[프로그래머스] 힙 : 더 맵게 Java

배열에서 가장 낮은 숫자와 그 다음으로 낮은 숫자 2개를 찾는다.

 

그 이후 공식에 맞게 조합해서 배열에 넣고 다시 가장 작은 숫자 2개를 찾는 것을 반복한다.

 

그런데 여기서 배번 배열을 탐색하는 것은 효율성 측면에서 떨어지고 배열에서 원소를 빼고 넣는 다는 것은 어려운일이다.

 

그래서 힙을 사용해서 푼다!

 

Max Heap은 가장 큰 숫자부터 차례대로 얻을 수 있는 자료구조이고 Min Heap은 가장 작은 숫자부터 얻을 수 있는 자료구조이다.

 

보통은 트리나 배열로 Heap을 구현하긴 하는데 우리는 이미 만들어진 자료구조를 사용할 것이다.

 

Max Heap을 다른 자료구조로 PriorityQueue 와도 같다.

 

PriorityQueue는 우선 순위 큐로서 가장 작은 숫자가 우선시 되게 기본으로 구현되어있다.

 

즉, Min Heap이 구현되어 있는 것이다. Max Heap으로 사용하고 싶다면 Comparator로 내림차순 설정도 가능하다.

 

친절하게 Java에는 PriorityQueue가 util에 구현되어 있다. 물론 코틀린에서도 사용 가능하다.

 

우리는 입력 받은 데이터를 PriorityQueue에 넣어서 poll을 통해 정렬이나 배열 탐색 없이 가장 작은 원소들을 빼올 것이다.

 

그 후 offer를 통해 Queue에 다시 넣어주고 스코빌 지수가 조건을 만족할 때까지 반복해줄 것이다!

 

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        PriorityQueue<Integer> scovilleQueue = new PriorityQueue<>();
        
        for(int i = 0; i < scoville.length; i++){
            scovilleQueue.offer(scoville[i]);
        }
        
        while(scovilleQueue.peek() < K){
            if(scovilleQueue.size() == 1){
                return -1;
            }
            int first = scovilleQueue.poll();
            int second = scovilleQueue.poll();
            
            scovilleQueue.offer(first+second*2);
            answer++;
        }
        
        return answer;
    }
}