[프로그래머스] 더 맵게 - JAVA

[프로그래머스] 더 맵게 - JAVA

이 문제는 가장 작은 두 수를 뽑으라는 말을 보자마자 우선순위 큐를 생각했습니다.

우선순위 큐는 큐와 다르게 FIFO 방식이 아니라 우선순위가 높은 원소가 먼저 제거되는 큐입니다.

우선순위가 가장 높은 값 = 스코빌 지수가 가장 낮은 값

우선순위가 그 다음으로 높은 값 = 스코빌 지수가 두번째로 낮은 값

을 대입해서 연산을 진행합니다.

원래의 값을 새로운 값으로 대체해야하므로 peek()이 아닌 poll()을 사용합니다.

 

public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i : scoville){
            queue.offer(i);
        }
        while (queue.peek() <= K){
            if (queue.size() == 1){
                return -1;
            }
            int a = queue.poll();
            int b = queue.poll();

            int result = a + (b*2);
            queue.offer(result);
            answer++;
        }

        return answer;
    }

 

Java에서 제공하는 PriorityQueue 를 사용했습니다.

우선 scoville 배열에 들어온 숫자들을 큐에 넣어줍니다.

큐의 맨 첫 원소를 삭제하지 않고 가져오는 peek()함수를 사용하여 K보다 작으면 while문을 계속 돌립니다.

그 후 예외처리 한 번 해주고, poll()함수를 사용하여 첫번째 원소를 삭제하면서 가져옵니다.

그 후 offer를 통해 result를 큐에 넣어줍니다.