[프로그래머스] 더 맵게 (Java)

 

프로그래머스

길이가 길고 주어진 숫자가 큰데 반해 뽑아서 사용해야하는 숫자는 가장 작은 두 개였기 때문에 효율적인 정렬을 위해 우선순위 큐(PriorityQueue)를 사용해서 문제를 해결했다.

 

- scoville 배열을 우선순위 큐에 삽입

- (최소 스코빌 지수가 K보다 작으면서 2개 이상 스코빌지수가 남아있는 동안 반복하여) 가장 작은 두 수를 추출하여 혼합 후 다시 큐에 삽입

- 반복문 종료 후에도 최소 스코빌 지수가 K보다 작으면 실패, 아니면 성공

 

Note

- 처음에 트리맵을 떠올렸는데, 둘을 비교해서 찾아보니 트리맵은 최대값과 최소값을 동시에 구해야 하거나 특정 키값을 기준으로 탐색이 필요한 경우에 사용하는 것이 좀 더 적합하다는 걸 알게되었다. 그리고 우선순위 큐는 느슨한 정렬인 상태로 정렬된 상태에서의 전체 탐색은 불가능하다. 나중에 비교해서 정리해보는 것도 좋을 것 같다.

import java.util.*;

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