[프로그래머스/자바] 더 맵게 풀이

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

프로그래머스

 

프로그래머스 코딩테스트 고득점 Kit의 힙 Level 2 문제다.

 

 

우선순위 큐는 힙의 원리와 동일하므로 자바의 PriorityQueue 라이브러리를 사용했다.

우선순위 큐에 scoville[] 원소를 넣으면 자동으로 가장 맵지 않은 두 음식의 스코빌 지수가 맨 앞으로 정렬될 것이다.

큐의 맨 앞 두개를 꺼내 새로운 음식을 만들고, 다시 큐에 넣는다.

 

큐의 가장 맨 앞의 원소가 가장 작은 스코빌 지수이므로,

맨 앞의 원소가 K보다 크면 큐의 모든 원소가 K보다 큰 것이다.

즉, while문을 통해 큐의 맨 앞 원소가 K보다 커질 때까지 반복한다.

 

큐의 원소가 두개 이상일 때만 새로운 음식을 만들 수 있다.

즉, 큐의 원소가 한개가 될때까지 반복문을 빠져나오지 못했다면

모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우이므로 -1을 return한다.

 

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        
        for(int i=0;i<scoville.length;i++) {
            q.offer(scoville[i]);
        }
        
        int cnt = 0;
        
        while(q.peek() < K) {
            if(q.size() == 1)
                return -1;
            
            int first = q.poll();
            int second = q.poll();
            
            q.offer(first + second * 2);
            cnt++;
        }
        
        return cnt;
    }
}