백준 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);
    }
}

 

조금만 생각의 전환을 하면 정말 쉽게 풀 수 있는 문제인데, 왜 난 매번 어렵게 돌아 돌아 생각을 하게 되는 걸까..

 

문제를 풀기 전에 한 가지 방법만 떠올리고 바로 코드로 들어가지 않고

방법을 천천히, 어떻게 구현할 것인지 작성하고 시간 복잡도를 계산해 본 뒤 코드 작성에 들어가는 습관을 기르도록 하자..ㅜㅜ