[프로그래머스] 더 맵게 (Heap)

문제 소개

오늘 풀었던 프로그래머스 - 더 맵게 문제를 정리합니다.

이 문제는 스코빌 지수가 낮은 음식부터 두 개를 섞어 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 필요한 최소 섞기 횟수를 구하는 문제입니다.

문제 링크: 더 맵게 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

 

1. 가장 낮은 두 음식의 스코빌 지수를 뽑아서 새로운 음식으로 만들고, 다시 섞어야 하므로
2. 매번 최소값을 효율적으로 뽑기 위해 우선순위 큐(최소 힙) 사용
3. 조건을 만족할 때까지 반복하고, 모든 음식이 K 이상인지 확인(최소값 >= K) 후 정답 반환

 

---

해결 과정 및 코드

핵심 아이디어

1. 최소 힙을 사용해 가장 작은 스코빌 두 개를 빠르게 추출
2. 새 스코빌 = a + b * 2 형식으로 생성
3. 새 음식을 다시 큐에 넣고 섞은 횟수 1 증가
4. 반복 종료 후에도 최소값이 K보다 작다면 → 불가능한 경우 -1 반환

코드

시간 복잡도 : O(N log N)

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int s : scoville) {
            heap.add(s);
        }
		
        // 더이상 섞지 못할 때 or K 미만의 스코빌 음식이 없을 때까지 반복
        while (heap.size() > 1 && heap.peek() < K) {
            int first = heap.poll();       // 가장 맵지 않은 음식
            int second = heap.poll();      // 두 번째로 맵지 않은 음식
            int mixed = first + (second * 2); // 섞은 후 새로운 스코빌 수치
            heap.add(mixed);
            answer++;
        }

        // 현재 음식의 최소 스코빌 지수값이 K 이상인지 확인
        if (heap.peek() < K) return -1;
        return answer;
    }
}