[프로그래머스] 더 맵게_JAVA

문제 링크

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

코딩테스트 연습 - 더 맵게

우선 순위 큐를 알면 쉽게 풀 수 있는 문제

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

우선순위 큐에 스코빌 지수가 담긴 음식들을 넣으면, 루트노드 : 가장 맵지 않은 음식의 스코빌 지수 가 된다.

따라서 큐에서 값을 두개 꺼내면 해당 공식의 인자를 구할 수 있으므로

두 음식을 섞어 다시 큐에 집어 넣으며 루트 노드가 K이상일 경우 or 더는 섞을 음식이 없을 경우까지 반복하면 된다.

 

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

우선순위 큐에 대한 자료구조 이해가 있으면 쉽게 풀이할 수 있는 문제였다.