Level2 - 더 맵게 (Heap)

스코빌 지수가 특정값에 못미치면 계속 그 작은값을 수식에 맞춰 더해가는 과정

입출력 예 설명

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회입니다.

 

스코빌의 길이가 백만까지 있는걸 봐서 일반 반복문으로 하면 통과가 안될거라 생각

리스트에서 작은 값을 계속 확인해서 새로운 값을 만든다? -> PriorityQueue 사용

 

 PriorityQueue란

최소힙을 만들어 준다.( 삽입이 되고 부모보다 작은 값이면 부모랑 값을 바꾼다.)

최소힙 이란 완전이진트리 형식으로 힙이 만들어지고 값이 가장 작다면 루트에 최소값이 저장.

내부구조가 힙으로 구성되어 있기에 시간 복잡도는 O(NLogN)

 

*일반적으로 PriorityQueue를 선언하면 최소힙으로 동작*

최대힙으로 -> PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());

 

 

코드

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

        return cnt;
    }
}