[Algorithm: 힙] 프로그래머스 <더 맵게>

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42626?language=java

프로그래머스

 

 

---

 

문제 설명

모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 가장 맵지 않은 두 개의 음식을 섞는 과정을 반복하는 문제이다.

 

섞는 방식은 다음과 같다.

새로운 음식 = 가장 작은 값 + (두 번째로 작은 값 * 2)

 

이 과정을 최소 횟수로 수행해야 하며, 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없다면 -1을 반환한다.

 

처음 접근

처음에는 리스트를 활용해서 정렬 후 앞에서부터 두 개를 꺼내는 방식으로 접근했다.

List<Integer> scovilleList = new ArrayList<>();

for (int s : scoville) {
    scovilleList.add(s);
}

Collections.sort(scovilleList);

while (scovilleList.get(0) < K) {
    int result = scovilleList.get(0) + 2 * scovilleList.get(1);
    scovilleList.remove(0);
    scovilleList.remove(0);
    scovilleList.add(0, result);
    Collections.sort(scovilleList);
}

 

가장 작은 두 값을 계속 사용해야 하기 때문에 정렬된 상태를 유지하면 해결할 수 있다고 생각했다.

 

---

문제점

이 방식은 로직 자체는 맞지만, 효율성 테스트 케이스를 통과하지 못했다. 

1. remove(0)의 비용

ArrayList에서 remove(0)을 하면 뒤에 있는 모든 요소를 한 칸씩 당겨야 한다.

따라서 한 번 실행할 때마다 O(n)이 발생한다.

 

2. 반복적인 정렬

매번 새로운 값을 넣고 다시 정렬을 수행했다.

Collections.sort(scovilleList);

 

이 연산은 O(n log n)이고, 이를 반복문 안에서 계속 수행하기 때문에 전체 시간 복잡도가 매우 커진다.

 

 

따라서

• 앞에서 삭제 → O(n)
• 정렬 반복 → O(n log n)

입력 크기가 최대 1,000,000이기 때문에 이 방식으로는 효율성 테스트를 통과할 수 없었다.

 

---

 

해결 방법

이 문제를 다시 보면 핵심은 다음과 같다.

• 가장 작은 값 2개를 계속 꺼낸다
• 새로운 값을 다시 넣는다

전체 정렬이 아니라 "최소값만 빠르게 꺼낼 수 있는 구조"가 필요하다

 

이 조건에 맞는 자료구조가 바로 PriorityQueue(최소 힙)이다.

 

PriorityQueue이란?

PriorityQueue는 이름 그대로  "우선순위 큐"이다.

 

일반적인 큐는 먼저 들어온 데이터가 먼저 나오는 구조(FIFO)이지만, PriorityQueue는 우선순위가 높은 데이터가 먼저 나오는 구조이다.

자바에서 기본적으로 사용하는 PriorityQueue는 값이 작은 순서대로 우선순위를 가지는 최소 힙 구조이다.

 

힙(Heap) 구조

힙은 트리 구조처럼 보이지만 실제로는 배열 기반으로 구현된 자료구조이다.

 

특징은 다음과 같다.

• 완전 이진 트리 구조를 따른다
• 부모 노드는 항상 자식 노드보다 작거나 같다. (최소 힙 기준)
• 전체가 정렬된 상태는 아니지만 최솟값은 항상 루트에 위치한다

즉, 모든 값을 정렬하지 않아도 가장 작은 값 하나는 항상 빠르게 꺼낼 수 있도록 설계된 구조이다.

 

주요 메서드

PriorityQueue에서 자주 사용하는 메서드는 다음과 같다.

pq.offer(x); // 값 추가
pq.poll(); // 가장 작은 값 제거 및 반환 (제거 O)
pq.peek(); // 가장 작은 값 조회 (제거 X)
pq.size(); // 크기 확인

이 두 연산이 반복적으로 사용된다.

 

시간 복잡도

PriorityQueue는 다음과 같은 시간 복잡도를 가진다.

• 삽입 (offer) : O(log n)
• 삭제 (poll) : O(log n)
• 조회 (peek) : O(1)

즉, 매번 정렬(O(n log n))을 수행하는 것보다 훨씬 효율적이다.

 

PriorityQueue 적용

PriorityQueue는 내부적으로 힙 구조를 사용하며, 항상 가장 작은 값이 먼저 나오도록 유지된다.

따라서 매번 정렬할 필요 없이 바로 최소값을 꺼낼 수 있다.

 

최종 코드

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) {
            if (pq.size() < 2) return -1;
            
            int first = pq.poll();
            int second = pq.poll();
            
            int mixed = first + second * 2;
            pq.offer(mixed);
            
            answer++;
        }
        
        return answer;
    }
}

 

 

 

---

시행착오

1. List로 접근한 것

처음에는 리스트 + 정렬 방식으로 풀었지만 효율성을 고려하지 못했다. 이 문제는 단순 구현이 아니라 자료구조 선택이 중요한 문제였다.

 

2. PriorityQueue 타입 지정

초기에 아래처럼 작성했다.

 

PriorityQueue pq = new PriorityQueue<>();

 

이 경우 반환 타입이 Object가 되어 연산이 불가능했다.

 

이를 해결하기 위해 제네릭을 명확히 지정했다.

PriorityQueue<Integer> pq = new PriorityQueue<>();

 

 

---

정리

이 문제는 단순히 값을 섞는 구현 문제가 아니라
자료구조 선택이 핵심인 문제였다.

• 전체 정렬이 필요한게 아니라
• 최소값만 계속 필요하다는 점을 파악하고 

이 기준으로 PriorityQueue를 선택해야 한다.

 

배운 점

• 시간복잡도를 고려하지 않으면 효율성에서 실패한다.
• ArrayList의 앞 삭제는 비용이 크다.
• PriorityQueue는 최솟값/최댓값 반복 처리 문제에서 유리하다.
• 코테에서는 문제보다 자료구조 선택이 더 중요한 경우도 많이 있다.