프로그래머스 42626번 더 맵게

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42626

풀이

최대값, 최소값이 나오는 문제는 Heap을 사용하면 됩니다.

Java에서는 Heap 대신에 PriorityQueue를 사용할 수 있습니다.

최소/최대값 확인: PriorityQueue.peek()

최소/최대값 추출 및 확인: PriorityQueue.poll()

 

시간 복잡도는 최초 항목 수만큼 순회하니 n, n-1만큼 순회하면서 최소값 2개 뽑고(2), 계산된 스코빌 값을 다시 add(logn) 하므로, n + n(2 + logn) = O(3n + nlogn) 이 되겠습니다. 배열을 사용했으면 O(n^2)가 되었을 것입니다.

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();//minHeap
		//Heap에 초기값 입력
        for(int i = 0; i < scoville.length; ++i) {
            minHeap.add(scoville[i]);
        }
		
        while(minHeap.size() > 1) {
            int min1 = minHeap.poll();
            int min2 = minHeap.poll();
            answer++;
            minHeap.add(min1 + (min2 * 2));//스코빌 계산
            if(minHeap.peek() >= K) return answer;//최소값으로 확인
        }
        return -1;
    }
}