13. 프로그래머스 - 더 맵게 (힙)

문제 설명
매운 음식을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶어합니다. 이를 위해 Leo는 가장 맵지 않은 두 음식을 아래와 같은 방법으로 섞어 새로운 음식을 만듭니다.

 

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

 

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 이 과정을 반복합니다.

 

주어진 정보

• 음식의 스코빌 지수가 담긴 배열 scoville
• 원하는 스코빌 지수 K

목표
모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 반환하는 solution 함수를 구현하세요.

조건

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

입출력 예시

scoville	K	return
[1, 2, 3, 9, 10, 12]	7	2

 

예시 설명

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를 사용하면 되는 문제이다.

 

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식 + (두 번째로 맵지 않은 음식 × 2) 이 식이 주어지면

 

while문을 이용해 PriorityQueue 값 중 제일 작은 값과 K를 비교했을 때 K값보다 클 때까지 계속 반복해주면 된다.

 

PriorityQueue는 기본적으로 minHeap의 특성을 가지고 있기 때문에 값을 넣게 되면 알아서 오름차순이 된다.

 

알고리즘 코드

import java.util.PriorityQueue;

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

 

if문과 같이 만약 pq의 사이즈가 2가 넘지 않은 경우는 -1을 반환하도록 작성해 주면 된다.

 

시간 복잡도 분석

최소 힙을 사용하여 가장 작은 두 값을 반복적으로 꺼내고 새 값을 삽입하는 방식으로 동작하므로, 전체 시간 복잡도는 O(N log N)이다.