🔍 프로그래머스 "더 맵게"
https://school.programmers.co.kr/learn/courses/30/lessons/42626?language=java
🎯 오늘의 학습 포인트
오늘은 자료구조 선택이 알고리즘의 성능과 코드 품질에 얼마나 큰 영향을 미치는지 깊이 있게 이해하게 됐다. 특히 값들을 정렬된 상태로 유지하면서 최소값을 반복적으로 찾아야 하는 상황에서는, 단순히 리스트를 매번 정렬하는 것보다 PriorityQueue를 사용하는 것이 훨씬 효율적이라는 점을 배웠다. 실제로 시간복잡도가 O(N²logN)에서 O(NlogN)으로 크게 개선되는 것을 경험했다.
문제 난이도가 높지 않아서 의도를 재차 재해석하면서 이 의도를 좀 더 명확히 드러내보려고 시도했다. 같은 결과를 내는 두 가지 접근 방식을 비교하면서, 코드가 문제의 의도를 얼마나 잘 표현하는지 고민해보기도 했다.
🚀 문제 해결 과정
처음 문제를 마주했을 때는 가장 익숙한 도구인 ArrayList를 선택했다. 마치 망치를 들고 있는 사람에게 모든 것이 못으로 보인다고, 그간 배열 위주로만 팼더니 모든 문제가 ArrayList로 해결될 것처럼 보였다. 아래와 같이 정렬을 통해 최소값을 찾으려고 시도했다.
List<Integer> scoville = new ArrayList<>();
for (int value : scovilleArray) {
scoville.add(value);
}
// 매 반복마다 정렬이 필요했다
scoville.sort((a,b)-> Integer.compare(a, b));
하지만 이 접근 방식에는 한계가 있었다. 마치 책장을 정리할 때마다 모든 책을 꺼내서 다시 정리하는 것처럼, 매번 두 개의 최소값을 찾아 새로운 값을 계산하고 나서는 전체 리스트를 다시 정렬해야 했다. 특히 리스트의 크기가 클수록 이런 반복적인 정렬 작업은 성능 저하를 초래했다.
🔄 시행착오와 개선
첫 시도에서 마주친 세 가지 문제점과 그것을 해결해 나간 과정은 다음과 같다.
- 입력 처리 방식의 혼동
백준 문제를 많이 풀다 보니 습관적으로 BufferedReader를 사용하려 했다. 프로그래머스는 이미 깔끔하게 포장된 매개변수로 입력을 제공하는데 말이다. - 인덱스 관리의 복잡성
ArrayList에서 요소를 제거할 때마다 모든 후속 요소들이 한 칸씩 이동해야 했고, 이는 O(N)의 추가 시간복잡도를 발생시켰다. 줄 서 있는 사람들 중 한 명을 빼내고 나머지 사람들을 앞으로 당기는 것과 같았다. 한 명을 빼낼 때마다 모든 사람이 한 걸음씩 앞으로 이동해야 했고, 이는 전체 성능에 큰 영향을 미쳤다.
- 비효율적인 정렬 프로세스
새로운 값을 추가할 때마다 전체 리스트를 다시 정렬해야 했던 것이 가장 큰 병목이었다. 마치 새로운 카드 한 장을 넣기 위해 매번 전체 카드를 다시 정리하는 것과 같았다. 이는 가장 큰 성능 저하의 원인이 됐다.
// 복잡한 인덱스 관리가 필요했던 코드
int firstMin = scoville.get(0);
scoville.remove(0);
int secondMin = scoville.get(0); // 이미 첫 번째 요소가 제거되어 인덱스가 밀림
scoville.remove(0);// 매 반복마다 필요했던 정렬
scoville.add(newScoville);
scoville.sort((a,b) -> Integer.compare(a,b)); // O(NlogN)의 시간복잡도
이러한 문제들은 PriorityQueue라는 더 적합한 도구를 찾으면서 자연스럽게 해결됐다. PriorityQueue는 내부적으로 이진 힙 구조를 사용하여 자동으로 정렬 상태를 유지하며, 최소값 추출과 새로운 값 추가가 모두 O(logN)의 시간복잡도로 가능해졌다.
우선순위 큐를 도입하니 확실히 이전 로직보다 훨씬 더 간결하고 효율적으로 만들 수 있었다. 이러한 개선 과정을 통해 적절한 자료구조 선택이 얼마나 중요한지를 직접 경험할 수 있었다. 덕분에 최소값을 찾고 새로운 값을 추가하는 모든 작업이 훨씬 효율적으로 이루어졌다.
머리로는 알고 있다고 생각한 개념도 실제로 써보기 전까지는 바로 떠올리지 못한다는 게 경험의 중요성을 새삼 깨닫게 해줬달까. 문제를 정말 다양하게 많이 풀어봐야겠다.
이러한 문제점들을 개선한 최종 코드는 다음과 같다.
import java.util.*;
class Solution {
public int solution(int[] scoville, int K) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int s : scoville) {
pq.offer(s);
}
int answer = 0;
while (pq.peek() < K && pq.size() >= 2) {
int first = pq.poll();
int second = pq.poll();
int newFood = first + (second * 2);
pq.offer(newFood);
answer++;
}
return pq.peek() >= K ? answer : -1;
}
}🔍 문제 요구사항 재분석
위 제출도 통과되긴 했다. 그런데 핵심 요구사항을 다시 꼼꼼히 읽어보니 "모든 음식의 스코빌 지수를 K 이상으로 만들기"를 좀 더 명확히 하고 싶었다.
처음 작성했던 코드는 이랬다.
while (pq.size() >= 2 && pq.peek() < K) {
// 섞기 로직
}
return pq.peek() >= K ? mixCount : -1;
이 코드를 보면서 다음과 같은 생각이 들었다.
"모든 음식이 K 이상이어야 하니까, K보다 작은 값이 하나라도 있으면 섞는 걸 계속해야 한다. 단, 음식을 섞으려면 두 개 이상의 음식이 필요하다. 그런데 만약 음식이 하나만 남았는데 그 값이 여전히 K 미만이라면? 이때는 더 이상 섞을 수가 없으므로 실패 케이스로 보고 -1을 반환해야 한다."
예시: K = 7, 현재 상태 = [3, 8, 9]
- 크기는 3이고 최소값(3)이 K(7)보다 작음
- 현재 로직으로는 계속 진행 가능하다고 판단
예시2: K = 7, 현재 상태 = [3]
- 크기가 1이라 while문 종료
- peek() >= K 조건만 확인하고 -1 반환
그래서 코드를 다음과 같이 손봤다.
while (pq.peek() < K) { // K보다 작은 값이 있으면 계속 시도
if (pq.size() == 1) { // 음식이 하나만 남았다면
return -1; // 더 이상 섞을 수 없으므로 실패
}
int first = pq.poll();
int second = pq.poll();
int newScoville = first + (second * 2);
pq.offer(newScoville);
mixCount++;
}
return mixCount;
비교하면,
이전 코드는 "두 개 이상의 음식이 있고, 동시에 K보다 작은 값이 있을 때" 계속 진행한다. "손님이 있고 주방이 열려있을 때 음식을 만든다"는 조건과 비슷하다. 얼핏 보면 깔끔해 보이지만, 문제의 본질적인 의도가 조건문 속에 다소 묻혀버린 느낌이다.
그에 반해
새 코드는 "K보다 작은 값이 있으면 계속 시도하되, 더 이상 시도할 수 없는 상황이면 실패"라는 문제 해결의 흐름을 그대로 담아냈다. "손님이 있으면 음식을 만들되, 주방이 닫혀있으면 중단한다"는 표현에 가깝다.
첫 번째 코드가 더 간결하고 두 코드의 실행 결과는 같지만, 두 번째 코드를 아래와 같은 이유로 좀 더 선호한다.
- 문제의 핵심 조건이 명확히 드러난다. "모든 음식의 스코빌 지수를 K 이상으로 만들기"라는 목표가 while 조건에서 바로 보인다.
- 실패하는 경우의 이유가 코드에 명시적으로 나타난다. 음식이 하나만 남았는데 여전히 K보다 작다면, 더 이상 섞을 수 없으므로 실패한다는 논리가 코드에 그대로 담겨있다.
- 나중에 코드를 수정하거나 디버깅할 때도 유리하다. 실패 조건이 추가되거나 변경되어야 할 때, if문 내부만 수정하면 되므로 코드 변경의 범위가 명확하다.
// 최종
import java.util.*;
class Solution {
public int solution(int[] scoville, int K) {
// 최소 힙으로 구현된 우선순위 큐 생성
PriorityQueue<Integer> pq = new PriorityQueue<>();
// 모든 스코빌 지수를 큐에 넣기
for (int s : scoville) {
pq.offer(s);
}
int mixCount = 0;
// K보다 작은 값이 있는 한 계속 섞기 시도
while (pq.peek() < K) {
// 음식이 하나밖에 없는데 K보다 작다면
// 더 이상 섞을 수 없으므로 실패
if (pq.size() == 1) {
return -1;
}
// 가장 맵지 않은 두 음식 꺼내기
int first = pq.poll();
int second = pq.poll();
// 새로운 스코빌 지수 계산하여 추가
int newScoville = first + (second * 2);
pq.offer(newScoville);
mixCount++;
}
// while문을 빠져나왔다는 것은
// 모든 음식의 스코빌 지수가 K 이상이 되었다는 의미
return mixCount;
}
}📚 핵심 개념 정리
PriorityQueue에서 가장 중요한 메서드는 peek(), poll(), offer()이다.
peek()는 최소값을 확인만 하고,poll()은 최소값을 추출하며 제거한다.offer()는 새로운 값을 추가한다.
// 기본 생성 (오름차순)
PriorityQueue<Integer> pq = new PriorityQueue<>();
// 내림차순 정렬
PriorityQueue<Integer> reversePq = new PriorityQueue<>(Collections.reverseOrder());
// 커스텀 정렬
PriorityQueue<Student> customPq = new PriorityQueue<>((s1, s2) ->
s1.getScore() - s2.getScore());
// 1. 추가 관련 메서드
pq.offer(value); // 요소 추가 (실패시 false 반환)
pq.add(value); // 요소 추가 (실패시 예외 발생)
// 2. 삭제 관련 메서드
pq.poll(); // 첫 번째 요소 제거하고 반환, 비어있으면 null
pq.remove(); // 첫 번째 요소 제거하고 반환, 비어있으면 예외
pq.clear(); // 모든 요소 제거
// 3. 조회 관련 메서드
pq.peek(); // 첫 번째 요소 반환, 비어있으면 null
pq.element(); // 첫 번째 요소 반환, 비어있으면 예외
// 4. 상태 확인 메서드
pq.size(); // 요소 개수 반환
pq.isEmpty(); // 비어있는지 확인
특히 코딩테스트에서는 예외 상황까지 고려할 필요가 적으므로, offer(), poll(), peek()의 조합이 가장 안전하고 편리하다. 실제 프로젝트에서는 상황에 따라 더 엄격한 체크가 필요한 경우 add(), remove(), element()를 사용할 수 있다.
시간복잡도 측면에서 ArrayList 방식은 O(N²logN)인 반면, PriorityQueue 방식은 O(NlogN)으로 훨씬 효율적이다.
ArrayList 방식의 시간복잡도
ArrayList로 구현할 경우, 매 반복마다 다음과 같은 연산이 필요하다.
- 정렬 수행 (Collections.sort 또는 list.sort) - O(NlogN)
- 최소값 두 개 제거 (remove) - 각각 O(N)
- 새로운 값 추가 (add) - O(1)
이 과정이 N번 반복될 수 있으므로
- 한 번의 반복에서: O(NlogN) + O(N) + O(1)
- N번 반복하면: O(N) × (O(NlogN)) = O(N²logN)
예를 들어 N이 1,000일 경우
// ArrayList 방식
for (int i = 0; i < N; i++) { // N번 반복
list.sort(...); // NlogN
int first = list.remove(0); // N
int second = list.remove(0); // N
list.add(first + (second * 2)); // 1
}
// 총 연산 횟수 ≈ 1000 × (1000 × log(1000) + 2000 + 1)
PriorityQueue 방식의 시간복잡도 분석
반면 PriorityQueue는 이진 힙 구조를 사용하여 다음과 같은 연산을 수행한다.
- 최소값 추출 (poll) - O(logN)
- 새로운 값 추가 (offer) - O(logN)
이 과정이 N번 반복되므로
- 한 번의 반복에서: O(logN) + O(logN) + O(logN)
- N번 반복하면: O(N) × O(logN) = O(NlogN)
예를 들어 N이 1,000일 경우
// PriorityQueue 방식
for (int i = 0; i < N; i++) { // N번 반복
int first = pq.poll(); // logN
int second = pq.poll(); // logN
pq.offer(first + (second * 2)); // logN
}
// 총 연산 횟수 ≈ 1000 × (3 × log(1000))실제 성능 차이 의미
N이 큰 경우(예: 100,000) 두 방식의 실제 연산 횟수 차이는 매우 커진다...
- ArrayList: 100,000² × log(100,000) ≈ 1,660,964,047,000회
- PriorityQueue: 100,000 × log(100,000) ≈ 166,096회
이는 PriorityQueue가 ArrayList에 비해 약 10,000배 더 효율적일 수 있다는 것을 의미한다. 이러한 차이는 입력 크기가 커질수록 더욱 극명해지며, 이는 왜 이 문제에서 PriorityQueue를 사용하는 것이 훨씬 더 적절한지를 잘 보여준다.
💭 회고
이번 문제를 통해 적절한 자료구조 선택의 중요성을 새삼 느꼈다. 처음에는 익숙한 ArrayList로 접근했으나, PriorityQueue를 사용함으로써 코드가 간결해지고 효율성이 크게 향상되었다. 특히 가장 작은 값을 반복적으로 찾아야 하는 패턴이 보일 때 PriorityQueue를 고려해볼 수 있다는 점을 배웠다.
의도를 명확히 드러내려고 수정해보면서 단순히 "작동하는 코드"를 넘어서 "의도가 명확한 코드"를 작성하는 게 중요하다고 새삼 다시 깨달았다. 사실 코딩 테스트는 제한된 복잡도 내 돌아가게 하면 되긴 하지만, 사실 내 작성의도가 다른 사람에게도 납득이 되기도 해야 하니까. 코드는 컴퓨터를 위한 명령어이기도 하지만, 동시에 다른 개발자(혹은 미래의 나)와 소통하는 도구이기도 하다. 따라서 문제의 본질적인 의도를 코드에 잘 담아내는 것이 매우 중요하다. 기술 인터뷰할 때 대비해 내 의도를 잘 전달하는 연습한 거라고 생각한다.
앞으로도 코딩 테스트 문제를 풀 때는 단순히 정답을 맞히는 것에서 그치지 않고, 문제의 의도를 가장 잘 표현할 수 있는 방법이 무엇일지 고민하는 습관을 들여야겠다.
다음 학습에서는 우선순위 큐를 활용하는 다른 문제들을 더 풀어보며 이 자료구조의 활용법을 깊이 있게 익혀볼 계획이다.
'DSA > 코딩테스트' 카테고리의 다른 글
| 99클럽 코딩테스트 스터디 5기 수료 자세한 후기 (0) | 2025.02.25 |
|---|---|
| 99클럽 코테 스터디 22일차 TIL - Java 백준 18870 좌표 압축 (1) | 2025.02.18 |
| 배열로 시작하는 코딩테스트 첫걸음: 시행착오와 성장의 기록 (1) | 2025.02.04 |
| 그래프 알고리즘 BFS & DFS 정복 feat. 백준 2573번 빙산 찾기, Softeer 장애물 인식 (2) | 2025.02.04 |
| 99클럽 코테 스터디 9일차 TIL - Java 백준 31562 전주 듣고 노래 맞히기 (2) | 2025.01.24 |