[프로그래머스] Lv.2 : 더 맵게 - 자바[Java]

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

프로그래머스

풀이

우선순위 큐(PriorityQueue)를 사용하면 쉽게 풀 수 있는 문제다.

 

로직

1. 모든 음식의 스코빌 지수를 PriorityQueue에 넣는다. PQ를 사용하면 자동으로 스코빌 지수가 작은 순대로 정렬된다.

2. PQ의 크기가 2이상이라면 다음 과정을 반복한다.

- pq.poll()을 통해 2개를 꺼낸다.

- 첫번째가 K보다 크다면 flag = true로 변경하고 break

- 새로운 음식의 스코빌 지수를 PQ에 넣는다.

- cnt++

3. flag가 false이면서 남아있는 음식의 스코빌 지수가 K보다 작다면 cnt = -1

4. cnt를 반환한다.

 

코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int cnt = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for (int s: scoville) {
            pq.add(s);
        }
        
        boolean flag = false;
        while (pq.size() >= 2) {
            int a = pq.poll();
            int b = pq.poll();
            
            if (a >= K) {
                flag = true;
                break;
            }
            
            int num = a + (b*2);
            pq.add(num);
            cnt++;
        }
        
        if (!flag && pq.poll() < K) {
            cnt = -1;
        }
        return cnt;
    }
}