[프로그래머스] 더 맵게 - Priority Queue(우선순위 큐)

우선 순위 큐(Priority Queue) 자료구조를 기억하고 있으면 쉽게 풀 수 있는 문제였다.

 

프로그래머스 더 맵게 문제

코딩테스트 연습 - 더 맵게

 

문제는

모든 음식의 스코빌 지수를 K 이상으로 만들고 싶어한다.
모든 음식의 스코빌 지수를 K이상으로 만들기 위해서는 스코빌 지수가 가장 낮은 두 개의 음식을 특별한 방법으로 섞어서 새롭게 만들 수 있다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

이 과정을 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞는다.
여기서 모든 음식의 스코빌 지수가 K 이상이 되기까지 섞는 최소 횟수는 몇 번인지 구하는 문제이다.

 

이 문제를 풀면서 처음 생각했던게 우선순위 큐이기는 하나 Java에 있는 자료구조를 활용하지 않고 단순하게 접근하려고 했다.

그러다보니 매번, Sorting을 진행하면서 시간초과가 났다.

 

우선순위 큐가 미리 구현되어있는 것을 찾고 쉽게 풀 수 있었던 문제이다.

 

그러나 우선순위 큐를 직접 구현하기 위해 Max Heap, Min Heap을 사용했다는 것을 자료구조 시간에 들었던 것이 기억은 났으나 아른아른거렸따..

다시 정리해봐야할 것 같다.

 

풀이 방법은 그냥 제일 작은 스코빌 지수가 >= K가 될 때가지 반복하고 그 과정을 반복했을 때, 마지막 가장 작은 숫자가 K 이상인지 판별하면 됐다.

 

전체 코드는

import java.util.*;

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