[알고리즘 / JAVA] 더 맵게 (프로그래머스)

더 맵게

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

문제 링크

핵심 아이디어

• 가장 작은 수와 2번 째로 작은 수를 골라내기 위한 힙 / 우선순위 큐
• 더 이상 섞을 수 없는 조건

코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // priority queue 생성
        for (int i : scoville) {
            pq.add(i);
        }

        while (true) {
            // 최소치를 넘은 경우 종료
            if (pq.peek() >= K) break;
			
            // 더 이상 섞을 수 없는 경우 -1 후 종료
            if (pq.size() == 1) {
                answer = -1;
                break;
            }
            
            // 2개를 뽑아 섞고 다시 삽입
            pq.add(pq.poll() + pq.poll() * 2);
            answer++;
        }
        
        return answer;
    }
}

한줄평

힙 / 우선순위 큐를 사용해야한다는 생각이 든 순간 이미 풀린 문제