더 맵게_복습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 로 해결했다. 이번 문제를 풀며 "있는 것을 활용하자" 라는 생각이 들었다. 다른 사람들이 만들어 놓은 라이브러리를 적극 활용하면 내가 직접 짠 코드보다 훨씬 더 효율적인 코드를 짤 수 있다.