[프로그래머스] 더 맵게

https://programmers.co.kr/learn/courses/30/lessons/42626?language=java 

코딩테스트 연습 - 더 맵게

2021-07-30

---

import java.util.*;
class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
 
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int j : scoville) pq.offer(j);
 
        while(pq.size() > 0) {
            int one = pq.poll();
            if(one >= K) break;
            if(pq.size() == 0) return -1;
            int two = pq.poll();
            int tmp = one + two * 2;
            pq.offer(tmp);
            answer++;
        }
 
        return answer;
    }
}

#문제풀이

PriorityQueue를 이용하였다. 

 

while문을 돌 때, 처음에 하나를 뽑는다. 이 때, K 이상이면 바로 함수를 끝낸다. 이미 정렬 된 상태 이므로, 가장 낮은 숫자가 조건을 만족하면 다음 숫자들도 마찬가지 일 것이다.  

 

그리고 pq에 하나도 안 남으면 스코빌 지수를 섞을 수 없으므로, 더 이상 만들 수 없는것으로 판단하여 -1을 리턴한다. 

 

pq에 아직 값이 남아있는데 만약 아직 조건을 만족하지 못한다면, 두 번째 낮은 값을 꺼내 계산해주고 다시 pq에 offer 해준다.