더 맵게(java)

문제설명

생각하기

1. scoville의 길이가 최대 1,000,000이기 때문에 최소값을 바로 찾는 PriorityQueue 최소힙을 사용한다.
2. 최소값이 k보다 작을때 반복하며 원소가 하나 남았을땐 -1을 리턴

내 풀이

import java.util.PriorityQueue;
class Solution {
    public int solution(int[] scoville, int K) {
        int ans = 0;
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        
        for( int i : scoville) heap.offer(i);
        
        while(heap.peek() < K){
            if(heap.size() == 1) return -1;
            
            int a = heap.poll();
            int b = heap.poll();
            int sum = a + ( b * 2 );
            heap.offer(sum);
            ans++;
        }
        return ans;
    }
}

데이터의 크기가 크고 그 중 최소값 2개를 뽑아 더해야하는 문제이므로 우선순위 큐를 생각해야한다.
java에서 PriorityQueue는 이진트리를 사용하여 시간복잡도 N(1)에서 최대 N(LogN)이 걸린다.
PriorityQueue의 기능을 보자
.peek() -> 가장 우선순위가 높은 원소를 가져온다. ( 추가한 값은 우선순위에 맞게 정렬이 된다)
.offer() ->queue에 원소를 집어 넣는다.
.poll() -> 가장 우선순위가 높은 원소를 반환한다.
.remove() -> 가장 우선순위가 높은 원소를 삭제한다.
.size() -> queue의 크기를 반환한다.

이 기능들을 이용해 문제를 푼다면 어렵지 않은 문제였다.