[프로그래머스][Lv.2][Java][Heap] 더 맵게

문제

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

프로그래머스

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

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

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

 

풀이

import java.util.*;

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

 

시간 복잡도

1. PriorityQueue<Integer> pq = new PriorityQueue<>(): 우선순위 큐를 초기화하는 데 O(1)의 시간이 소요된다.

 

2. for (int s : scoville) pq.offer(s): scoville 배열의 모든 요소를 우선순위 큐에 넣는데 O(N * log(N))의 시간이 소요된다. 이는 각 원소를 큐에 삽입할 때 log(N) 시간이 걸리는데, 총 N번 수행되기 때문이다.

 

3. while(pq.peek() < K): 이 루프는 pq.peek() (가장 작은 Scoville 지수)가 K보다 작은 경우에 동작한다. 루프의 조건은 힙에서 가장 작은 값 확인에 O(1)의 시간이 걸리며, 루프 내부의 작업은 아래와 같이 동작한다.

• int first = pq.poll();: 우선순위 큐에서 가장 작은 Scoville 지수를 추출하는데 O(log(N))의 시간이 걸린다.
• int second = pq.poll();: 두 번째로 작은 Scoville 지수를 추출하는데도 O(log(N))의 시간이 걸린다.
• int mix = first + (second * 2);: Scoville 지수를 섞는 연산은 상수 시간이 소요된다.
• pq.offer(mix);: Scoville 지수를 다시 우선순위 큐에 삽입하는데 O(log(N))의 시간이 걸린다.
• answer++;: 단순한 증가 연산으로 상수 시간이 소요된다.

 

4. if (pq.size() == 1 && pq.peek() < K) return -1;: 큐의 크기와 peek 연산이 모두 상수 시간이 소요된다.

따라서 위 코드의 시간 복잡도는 주로 우선순위 큐 동작으로 인해 결정된다. 각 루프 반복에서 우선순위 큐에서의 poll() 및 offer() 연산이 O(log(N))의 시간을 필요로 하며, 이러한 루프는 최대 N번 반복됩니다. 따라서 전체 시간 복잡도는 O(N * log(N))이다.