[프로그래머스_JAVA_알고리즘] 더 맵게 #힙 #우선순위 큐

힙 문제는 우선순위 큐 Priority Queue를 이용해서 풀 수 있습니다.

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        
        for(int s: scoville)
            priorityQueue.add(s);
        
        int num = priorityQueue.peek();
        while(num < K){
            if(priorityQueue.size() >= 2){
                priorityQueue.add(priorityQueue.poll() + (priorityQueue.poll() * 2));
                num = priorityQueue.peek();
                answer++;
            }
            else
                return -1;
        }
        return answer;
    }
}

 

우선순위 큐를 이용하면 새로운 값을 삽입할 때 자동으로 정렬됩니다. 즉, 동적인 데이터 처리에 적합합니다.

먼저 모든 스코빌 지수를 priorityQueue에 넣습니다.

그 다음 데이터를 peek()해서 값을 조회합니다.

num < K일 때, priorityQueue 크기가 2 이상이라면 priorityQueue에 값을 넣습니다.

poll()을 통해 값을 꺼내와서 add()합니다.

그리고 다시 다음 데이터를 peek()해서 값을 조회하고, answer를 증가합니다.

num = priorityQueue.peek()을 한 번 더 하는 이유는 while(num < K)를 만족하기 위해서입니다.

 

.

.

.

 

문제는 아래에서 확인할 수 있습니다.

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

프로그래머스