[프로그래머스/Lv. 2] 더 맵게 (JAVA)

🔺 문제

프로그래머스

 

 

🔺 코드

import java.util.*;
 
class Solution {    
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int s : scoville) {
            pq.add(s);
        }
        
        while(pq.size() > 1 && pq.peek() < K) {
            int first = pq.poll();
            int second = pq.poll();
            
            int newScore = first + (second * 2);
            pq.add(newScore);
            
            answer++;
        }
        
        if(pq.peek() < K) // 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우
            return -1;
        
        return answer;
    }
}

 

🧩 해결 아이디어

• 우선순위 큐

1. 스코빌 배열 원소 값을 우선순위 큐에 넣어 자동 오름차순 정렬하게 한다.

2. 우선순위 큐 크기가 2 이상이고, 가장 작은 값이 K보다 작은 경우,

  가장 작은 값과 가장 큰 값을 이용해 새로운 스코빌 지수를 우선순위 큐에 저장하고, 섞은 횟수 +1한다.

 

3. 우선순위 큐 크기가 2개 미만이고, 가장 작은 원소가 K보다 작을 때,

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

그게 아니라면 섞은 횟수를 출력한다.

 

---

🔺 다른 풀이들

 

 

---

💬 느낀 점

 

1회독	2회독	3회독	4회독	5회독
V