더 맵게_복습

2026.08-11

문제 풀이

나의 코드

---

소요 시간: 49분
시간 복잡도: $O(nlogn)$

---

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        int cnt = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int k : scoville) {
            pq.add(k);
        }
        
        while(pq.peek() < K) {
            if (pq.size() < 2) {
                return -1;
            }
            int key1 = pq.poll();
            int key2 = pq.poll();
            pq.add(key1 + key2 * 2);
            cnt++;
        }
        
        return cnt;
    }
}

AI 코드

---

시간 복잡도: $O(nlogn)$

---

코드 분석

List<Integer> list = Arrays.stream(scoville).boxed().collect(Collectors.toList());

1. .stream()을 이용해 scoville[] 원소가 하나씩 흘러가는 통로를 만듦
2. boxed()를 이용해 IntStream을 Integer 객체로 포장함
3. .collect를 이용해 흘러가는 원소들을 실제 컬렉션에 모아 담음

---

PriorityQueue<Integer> pq = new PriorityQueue<>(list);   // O(n) heapify

add를 n번 호출 시, 힙 생성 비용은 O(n log n)이지만,
컬렉션을 한번에 받아 O(n)으로 생성이 가능함.

---

import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.stream.Collectors;

class Solution {
    public int solution(int[] scoville, int K) {
        List<Integer> list = Arrays.stream(scoville).boxed().collect(Collectors.toList());
        PriorityQueue<Integer> pq = new PriorityQueue<>(list);   // O(n) heapify

        int cnt = 0;
        while (pq.peek() < K) {
            if (pq.size() < 2) return -1;

            int first = pq.poll();
            int second = pq.poll();
            long mixed = (long) first + (long) second * 2;       // 오버플로 차단
            pq.add((int) Math.min(mixed, Integer.MAX_VALUE));    // K 이상이면 값 자체는 무의미
            cnt++;
        }
        return cnt;
    }
}

문제 풀이 후기

자동 정렬을 해주는 TreeMap으로 해결해보려 했으나 값의 삽입 및 삭제가 용이하지 않아 부적합하다고 판단했음.