백준 1202 보석 도둑
오랜만의 알고리즘 문제 풀이를 들고 돌아왔다.
결론적으로 말하면, 나 혼자 스스로 생각해 풀기로는 실패한 문제다 ;-;
다만 접근 방법을 알고 난 이후에 왜 난 이 방식을 생각 못했을까. 내가 생각한 방식의 순서만 바꿔도 훨씬 쉽게 접근할 수 있었는데..라는 생각이 들었다.
그래서 이건 기록해야한다! 라는 마음에 오랜만에 백준 문제를 블로그에 작성해 본다.
위 문제는 설명은 간단한 문제다.
세계적인 도둑 상덕이가 보석을 터는데, 각 C의 무게만큼을 담을 수 있는 가방 N개를 가지고 있다.
가방 1개당 1개의 보석밖에 넣지 못하고, 각 보석은 무게와 가격이 주어진다.
그래서 훔칠 수 있는 보석의 가장 큰 가격을 출력하는 방식이다.
오류
가장 처음 접근한 방식은 우선순위 큐 + 이진탐색을 이용한 풀이법이었다.
보석에서 가장 비싼 보석은 우선순위 큐로 뽑아내고,
보석이 들어갈 수 있는 가방 중 가장 작은 무게를 담는 게 가능한 가방을 찾기 위해 이진 탐색을 사용하고자 했다.
우선순위 큐로 보석을 찾는 건 어렵지 않았으나,
보석의 무게보다 큰 가방 중 가장 작은 무게를 담을 수 있는 가방을 찾는 것에 정말 시간이 많이 들었다.
문제
1. 일단 우선순위 큐에서 보석을 하나 꺼낼 때마다 매번 이진 탐색을 수행해서 가방을 찾는 과정이 while안에 while문을 또 쓰는 등 시간을 펑펑 사용했다.
2. 또한 이 경우 이미 사용한 가방인지 아닌지 확인하고 이를 또 배열에 따로 표기를 하면서 더더욱 복잡한 코드 + 수많은 if문을 가지게 되었다.
해결
해결 방법은 그냥 우선순위를 뒤바꿨다.
원래는 1. 가장 비싼 보석을 찾는다 → 2. 해당 보석을 담을 수 있는 가장 작은 가방을 찾는다
의 순서였다면, 새로운 방식에서는
1. 가방과 보석을 가장 작은 무게로 정렬한다 → 2. 현재 가방에 담을 수 있는 모든 보석을 큐에 넣고, 가장 가치 있는 보석을 선택한다.
의 순서로 진행된다.
원래방식에서는 큐로 보석을 찾고, 그 보석에 맞는 가방을 찾기 위해 이진 탐색을 돌렸지만
새로운 방식에서는 현재 선택한 가방에 들어갈 수 있는 모든 보석을 큐에 넣고, 가장 가치있는 녀석을 뽑으면 되는 것이다.
import java.io.*;
import java.util.*;
public class Main {
static class Jewel implements Comparable<Jewel> {
int weight, value;
Jewel(int weight, int value) {
this.weight = weight;
this.value = value;
}
@Override
public int compareTo(Jewel o) {
return this.weight - o.weight; // 무게 기준 오름차순 정렬
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine().trim());
int N = Integer.parseInt(st.nextToken()); // 보석 개수
int K = Integer.parseInt(st.nextToken()); // 가방 개수
Jewel[] jewels = new Jewel[N]; // 보석 배열
int[] bags = new int[K]; // 가방 배열
// 보석
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine().trim());
int M = Integer.parseInt(st.nextToken()); // 무게
int V = Integer.parseInt(st.nextToken()); // 가격
jewels[i] = new Jewel(M, V);
}
// 가방
for (int i = 0; i < K; i++) {
bags[i] = Integer.parseInt(br.readLine().trim());
}
// 1단계 : 보석 & 가방 정렬
Arrays.sort(jewels); // 보석은 무게 기준 오름차순 정렬
Arrays.sort(bags); // 가방도 무게 기준 오름차순 정렬
// 2단계 : 가장 비싼 보석을 뽑도록 우선순위 큐로 관리
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
long result = 0;
int jewelIdx = 0;
// 3단계 : 가방에 맞는 보석 선택
for (int bag : bags) {
// 현재 가방에 담을 수 있는 보석을 우선순위 큐에 추가
while (jewelIdx < N && jewels[jewelIdx].weight <= bag) {
pq.offer(jewels[jewelIdx].value);
jewelIdx++;
}
// 가능한 보석 중 가장 비싼 보석 선택
if (!pq.isEmpty()) {
result += pq.poll();
}
}
System.out.println(result);
}
}
조금만 생각의 전환을 하면 정말 쉽게 풀 수 있는 문제인데, 왜 난 매번 어렵게 돌아 돌아 생각을 하게 되는 걸까..
문제를 풀기 전에 한 가지 방법만 떠올리고 바로 코드로 들어가지 않고
방법을 천천히, 어떻게 구현할 것인지 작성하고 시간 복잡도를 계산해 본 뒤 코드 작성에 들어가는 습관을 기르도록 하자..ㅜㅜ