더 맵게_복습2

2026.09.28

문제 풀이

1차 실행 오류

---

83.9/100.0

효율성 테스트 시간 초과 오류

---

시간 초과 원인 분석

1,000,000 이하의 길이를 갖는 scoville 배열을
매번 sort() 를 통해 정렬하는 것이 원인이다.

---

import java.util.Collections;
import java.util.List;
import java.util.ArrayList;
import java.util.Comparator;

class Solution {
    public int solution(int[] scoville, int K) {
        int cnt = 0;
        List<Integer> scovilles = new ArrayList<>();
        
        for (int i = 0; i < scoville.length; i++) {
            scovilles.add(scoville[i]);
        }
        while(true) {
            scovilles.sort(Comparator.naturalOrder());
            int first = scovilles.get(0);
            if (first >= K) {
                break;
            }
            int second;
            try {
                second = scovilles.get(1);
            } catch (IndexOutOfBoundsException e) {
                return -1;
            }
            scovilles.remove(0);
            scovilles.remove(0);
            scovilles.add(first + second * 2);
            cnt++;
        }
        return cnt;
    }
}

2차 실행 오류

---

87.1/100.0

런타임 에러

---

런타임 에러 원인 분석

while 문은 내부 코드의 동작이 끝난 후 다시 시작할 때, 종료 조건을 검사한다.
따라서 첫번째 poll() 을 한 후에 queue 가 비어 있어도 종료하지 않고
두번째 poll() 을 진행하는데, 이 때 런타임 오류가 발생할 수 있다.

---

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        int cnt = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i < scoville.length; i++) {
            queue.add(scoville[i]);
        }
        while(!queue.isEmpty() && queue.peek() < K) {
            int first = queue.poll();
            int second = queue.poll();
            queue.add(first + second * 2);
            cnt++;
        }
        return cnt;
    }
}

나의 코드

---

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

---

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        int cnt = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i < scoville.length; i++) {
            queue.add(scoville[i]);
        }
        while(!queue.isEmpty() && queue.peek() < K) {
            int first = queue.poll();
            if (queue.isEmpty()) {
                return -1;
            }
            int second = queue.poll();
            queue.add(first + second * 2);
            cnt++;
        }
        return cnt;
    }
}

AI 코드

---

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

---

코드 분석

구조는 동일하다.

Arrays.stream(scoville).boxed().collect(Collectors.toList())

Arrays.stream()

• int 값들의 흐름으로 바꿈

• 결과: IntStream: 1, 2, 3, 9, 10, 12

.boxed()

• IntStreeam 의 int 를 하나씩 오토박싱 하여
  Integer로 바꿈

• PriorityQueue의 경우 제네릭이기 때문에 int를 담을 수 없음

• 결과: Stream<Integer>

.collect(Collectors.toList())

• 스트림의 원소들을 모아 List<Integer> 로 만듦

---

왜 하나씩 넣을 때에는 오토박싱이 적용되는데,
stream을 사용할 때에는 적용되지 않는가?

IntStream 은 int 만 다루는 전용 인터페이스이기 때문에
시그니처가 Stream<Integer> 와는 다름

---

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

class Solution {
    public int solution(int[] scoville, int K) {
        // 배열을 한 번에 넘기면 heapify로 O(N)에 힙 구성
        PriorityQueue<Integer> pq = new PriorityQueue<>(
            Arrays.stream(scoville).boxed().collect(Collectors.toList())
        );

        int cnt = 0;
        while (pq.peek() < K) {
            if (pq.size() < 2) return -1;   // 섞을 상대가 없음
            int first = pq.poll();
            int second = pq.poll();
            pq.add(first + second * 2);
            cnt++;
        }
        return cnt;
    }
}

문제 풀이 후기

처음 문제를 풀기 전, PriorityQueue 를 활용해서 푸는 문제라는 것을
깃허브 저장소의 README.md를 통해 알게 되었다.
하지만 정답을 알고 푸는 것은 시간 낭비라는 것을 알기에
다른 방법으로도 한번 접근해서 풀어보고자 했으나 결국 시간 초과 오류로 인해
실패하고 말았다.

결국은 PriorityQueue 로 해결했다.

이번 문제를 풀며 "있는 것을 활용하자" 라는 생각이 들었다.
다른 사람들이 만들어 놓은 라이브러리를 적극 활용하면 내가 직접 짠 코드보다
훨씬 더 효율적인 코드를 짤 수 있다.