[프로그래머스] (Java) 더 맵게 - 스코빌지수 (힙/Heap) Feat. 우선순위큐

 

📑 1. 문제설명

 

입출력 예 설명

 

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

 

2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
가진 음식의 스코빌 지수 = [13, 9, 10, 12]

 

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

---

💡 2. 접근방식

항상 정렬이 되어 있어서 낮은 순위부터 꺼낼 수 있는 우선순위 큐 사용

Priority Queue(우선순위큐)

배열을 우선순위 큐에 넣는다

큐 안에서 가장 낮은 숫자가 k 이상이 될 때 까지 가장 낮은 숫자 두 개 섞기

 

 

우선순위 큐에서 poll을 두 번 해 주면 가장 낮은 숫자와 두 번째로 낮은 숫자가 나온다

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

 

해당 수식을 수행하고 결과값을 다시 큐에 넣는다. 

가장 낮은 숫자를 다시 min 변수에 넣기

이 과정이 한 번 반복될때마다 cnt++ 해준다.

 

loop의 종료 조건은 큐의 가장 낮은 숫자가 K이상일 때 이기 때문에 따라서 while문은 min < K 때만 돌아간다.

또, 루프 안에서 queue가 2 이상일 때만  loop안의 계산식이 수행되어야 한다. 

큐의 크기가 1칸이면 계산이 불가하므로 -1 리턴해준다.

---

⭐ 3. 코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int cnt = 0;
        PriorityQueue<Integer> pqueue = new PriorityQueue<>();
        for (int s : scoville) {
            pqueue.add(s);
        }
        int min = pqueue.peek();
        while(min < K) {
            if(pqueue.size()>=2) {
                pqueue.add(pqueue.poll() + pqueue.poll() * 2);
                min = pqueue.peek();
                cnt++;
            } else {
                return -1;
            }
        }
        return cnt;
    }
}

---

👉🏻 4. 같은 유형 문제 (우선순위큐)

[프로그래머스] (Java) 프로세스 문제풀이 (스택/큐)

 

[프로그래머스] (Java) 디스크컨트롤러 (힙/Heap) 우선순위 큐