프로그래머스 - 42626번: 더 맵게 [Java]

문제: https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

1. 코드

import java.util.*;
class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue <Integer> queue = new PriorityQueue<>();
        for(int s : scoville)
            queue.offer(s);
        while(queue.peek() < K && queue.size() > 1) {
            queue.offer(queue.poll() + queue.poll() * 2);
            answer++;
        }
        return queue.peek() >= K ? answer : -1;
    }
}

2. 설명

int answer = 0;
PriorityQueue <Integer> queue = new PriorityQueue<>();
for(int s : scoville)
    queue.offer(s);

힙정렬을 하기 위해 PriorityQueue를 사용합니다. scoville에 있는 값을 우선순위 큐에 저장합니다.

while(queue.peek() < K && queue.size() > 1) {
    queue.offer(queue.poll() + queue.poll() * 2);
    answer++;
}

소스를 섞기 위해서는 최소 2개가 존재해야 하며 가장 작은 값과 두 번째로 작은 값을 가져와서 계산한 다음 다시 우선순위 큐에 저장합니다. 그리고 answer를 1 증가시킵니다.

return queue.peek() >= K ? answer : -1;

만약 우선순위 큐의 peek 값이 K 미만이라면 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우이기에 -1을 반환합니다. 아니라면 answer를 반환합니다.

3. 정리

• 문제에 대한 이해와 우선순위 큐를 사용한다면 쉽게 해결할 수 있다.

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges