[코딩테스트][백준] 🔥 백준 1202번 "보석 도둑" 문제: Python과 Java로 완벽 해결하고 면접 준비까지! 🔥

🔗 문제 링크

https://www.acmicpc.net/problem/1202

🛠️ 미해결

• 풀이시간 : 2시간 이상
• 그리디 문제라는 점을 기준으로 가장 작은 가방에서 가장 비싼 보석을 담는 다는 아이디어 자체는 그대로 생각하였다. 하지만 작은 가방부터 탐색하였을 때, 가장 비싼 보석을 담기 위해서 가치순으로 정렬을 하였지만 각 가방에 대해서 모든 보석을 전부 탐색해야 하므로 시간복잡도가 $O(n^2)$가 나와서 불가능하였다. 하지만 아이디어 자체는 맞다는 전제하에 시간복잡도를 줄이기 위한 노력으로 탐색범위를 한번만 돌기 위해 기준을 계속해서 찾기 위해 접근하였으나 범위를 줄이는 기준점을 찾지 못하였다.
• 왜 그렇다면 기준점을 찾지 못하였을까? 해당 범위를 탐색하고 무게나 가치등의 정렬 기준을 바꿔가면서 어떤 조건으로 찾아갈지를 생각하는것까지는 좋았으나 해당 조건에 맞는 보석들 즉, 특정 무게를 기준으로 담을 수 있는 모든 보석들에 대해서 찾는다는 것은 좋았으나 이 부분에서 범위를 줄이지를 못했다. 범위 기준이 커지는 점을 인식하여 해당 리스트 탐색에서 범위를 줄이는 아이디어가 한계였던 것이다. 다른 곳에 담아서 그 것을 탐색할 생각은 하지 못하였다.
• 왜 그렇다면 기준이 되는 것들을 빼놓고 그것을 따로 다룰 생각을 하지 못하였을까? 기준이 다음 기준을 포함하는 행위에서 탐색이 이어진다는 부분을 생각하지 못하였다.
• 왜 그랬을까? 앞에서의 탐색이 뒤에서의 탐색을 포함할 때, 이 중복부분을 없앤다는 것을 연습하지 않았고 생각조차 못하였다. 무조건 해당 기준으로 탐색하는 것만 생각하였다. 가치기준으로 정렬한 영향이 가장 컸다. 그리디의 영향으로 현재의 조건이 2개 이상일 때 한가지만 고려해서 정렬하고 다른 기준에 대한 것을 하나의 기준의 정렬에 맞추려는 이상한 습관이 있었기 때문이다. 그렇기 보다는 하나의 기준을 고려해놓고 다음 기준을 따로 빼놓거나 해서 하는 습관을 들여놔야겠다.

🕒 Python 풀이시간: x

import heapq

n,k=map(int,input().split())

jewels=[]
for _ in range(n):
    heapq.heappush(jewels,list(map(int,input().split())))

bags=[]
for _ in range(k):
    heapq.heappush(bags,int(input()))

tmp=[]
answer=0
while bags:
    bag=heapq.heappop(bags)
    while jewels and bag>=jewels[0][0]:
        heapq.heappush(tmp,-heapq.heappop(jewels)[1])
    if tmp:
        answer+=-heapq.heappop(tmp)
print(answer)

🕒 Java 풀이시간: x

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        long answer=0;
        int n=sc.nextInt();
        int k=sc.nextInt();
        int[] bags=new int[k];
        PriorityQueue<int[]> jewels=new PriorityQueue<>(Comparator.comparingInt(pair->pair[0])); 
        for(int i=0;i<n;i++){
            int m=sc.nextInt();
            int v=sc.nextInt();
            jewels.add(new int[]{m,v});
        }
        for(int i=0;i<k;i++){
            bags[i]=sc.nextInt();
        }
        Arrays.sort(bags);

        PriorityQueue<Integer> tmpPriorityQueue=new PriorityQueue<>(Collections.reverseOrder());
        for(int bag:bags){
            while(!jewels.isEmpty()&&bag>=jewels.peek()[0]){
                tmpPriorityQueue.add(jewels.poll()[1]);
            }
            if(!tmpPriorityQueue.isEmpty()){
                answer+=tmpPriorityQueue.poll();
            }
        }
        System.out.println(answer);
    }
}

📖 상세 설명 & 면접 대비

1. 문제 설명 : 각 N개의 보석에 대해 각 무게와 가치가 m,k가 n개가 주어지고 해당 보석를 하나씩만 담을 수 있는 가방 K개에 대해서 각 담을 수 있는 최대 무게치가 각 주어질 때, 담을 수 있는 보석의 가치의 최대 합을 구하는 문제이다.
2. 입력과 출력과 제약조건 : 이 경우는 K개의 가방에 대해서 N개의 보석을 담는 문제이며 이에 대해 무게는 조건으로 제한되는 경우이기 때문에 보석과 가방의 수를 시간복잡도에 포함될 것을 염두해두고 입력과 출력의 시간복잡도를 예상하면 된다. 보석과 가방의 수는 각 최대 300,000개 이므로 $O(NlogN)$ 이하의 시간복잡도를 사용하면 된다고 생각하면 된다.
3. 알고리즘 설명 : 그리디 알고리즘을 사용하는 문제이다. 그리디 알고리즘이란 현 단계에서 가장 최적이라고 생각되는 선택을 하는 알고리즘이다. 전체적인 방법에 대해서 본다면 가장 가치가 높은 보석을 가장 작은 가방에 담으면 되는 문제이다. 즉, 가방의 기준에서 생각한다면 작은 가방에서 부터 가장 비싼 보석을 담으면 최대 가치의 합이 커진다고 생각할 수 있다. 이 틀을 위해서 작은 가방부터 탐색하면서 해당 가방에 들어가는 보석을 전부 생각하면 된다. 작은 가방부터 들어가는 보석을 찾기 때문에 범위가 넓어지는 방식이므로 그 전에 탐색한 범위를 저장하면서 그 범위에서의 최대값을 구하기 위해 해당 범위의 최댓값을 넣고 꺼내는 대로 사용하는 최대 힙을 사용하면 된다. 그렇기에 남은 보석이 존재할 때, 작은 가치부터 보석을 꺼내서 현재 가방의 허용 무게보다 작다면 탐색범위에 포함시키면서 후에 가장 높은 가치를 쉽게 찾기 위해 최대 힙에 넣으면 된다. 이렇게 찾은 범위에서 보석들이 있다면 그 보석중 가장 높은 보석을 하나 꺼내서 정답에 더하면 된다.
4. 우선순위 큐를 사용하는 이유 : 이 이유는 두 가지인데 배열로도 범위의 탐색이 가능하지만 해당 인덱스를 기억하는 부분과 범위를 줄이는 이점 두가지를 동시에 얻을 수 있기 때문이다. 첫번째는 보석을 담는 큐인데 이 때 큐가 아닌 배열이라면 후에 조건을 확인할 때, 탐색한 범위까지의 인덱스를 기억해놔야한다. 두 번째는 최대 큐에 보석의 가치를 저장해 두는 것인데 이 때도 배열을 사용하는 경우 바로 정렬이 되지 않을 뿐더러 최대값만 필요한 처리를 수행할 수 없다.
5. 정렬을 하는 이유 : 정렬을 하는 이유는 그리디 알고리즘을 적용시킬 때, 가장 작은 가방에 가장 큰 가치의 보석을 담기 위해서이며 작은 가방부터 사용해야만 나중에 무게 대비해서 큰 가치의 보석을 큰 곳에 담을 수 있기 때문이다.
6. 알고리즘의 시간복잡도 : 우선순위 큐가 사용되는 부분에서 nlogn의 알고리즘이라고 볼 수 있다고 할 때, 탐색 부분은 가방을 전체적으로 한번 순회하면서 300,000에 중복 탐색이 아니라 보석 또한 한번만 순회되므로 600,000회라고 볼 수 있다. 이 때, 넣고 빼고의 우선순위 큐의 연산이 logn이므로 nlogn이라고 볼 수 있다.
7. 알고리즘의 공간복잡도 : 상수 공간복잡도로 계산되는 것을 제외하고 보석을 담는 우선순위 큐의 경우에는 O(n)의 공간복잡도를 가지고 가방의 공간에는 k개이기 때문에 O(n+k)라고 볼 수 있다. tmp의 경우에도 최악의 경우 보석이 다들어가므로 O(n)이므로 전체적으로 O(n+k)라고 공간복잡도를 볼 수 있다.
8. Comparator를 사용해 정렬하는 이유와 방법 : Java의 Comparator 인터페이스에서 제공하는 정적 메서드로 comparingInt를 사용할 수 있는데 이 때 이 함수는 정렬 기준 함수를 매개변수로 받는다. 이 때, pair는 람다함수에서 사용되는 익명 배열로 우선순위 큐의 저장 타입을 지정할 때, 타입이 결정된다. 이러한 함수는 Comparator타입을 생성자로 받아 우선순위 큐로 생성하면 정렬기준으로 생성된다. 기준뿐만 아니라 역순으로 삼고 싶으면 Comparator에 reversed()를 사용하면 역정렬순의 Comparator를 반환한다. Comparator자체가 제네릭 타입을 가지고 있고 이 것이 나중에 람다식을 설정할 때 같은 경우에 그대로 람다식 변수의 타입이 된다.
9. Collections.reverseOrder() : 이 때, 컬렉션의 reversorder 또한 Comparator 타입을 반환하여 우선순위 큐를 생성할 때, 정렬 순서를 지정해준다. 기존의 순서를 유지하려면 naturalOrder()를 사용한다.
10. 우선순위 큐의 원리 : 우선순위 큐는 이진트리 힙의 구조를 이용한다. 최소 힙을 기준으로 설명하자면 한 수가 추가 될 때, 이 수는 각 완전이진트리를 완성시켜가는 끝에 들어간다. 그런 후 부모의 노드보다 자식의 노드가 작은 형태로 상향 조절을 하는 식으로 추가된다. 반대로 삭제 시에는 가장 작은 수인 제일 위의 부모노드를 삭제하고 완전이진트리의 끝에있는 노드를 루트노드로 이동시킨다. 그런 다음, 하향 조절하면서 이진트리를 한다. 이런 조절시의 탐색단계가 반으로 줄어들기 때문에 logn의 시간복잡도를 가지는 것이다.
11. 다른 곳에서의 사용 : 만약 이 알고리즘이 다른 곳에서 사용된다면 작업스케줄링에 따른 이익문제에 사용될 수 있을 것 같다. 보석을 작업으로 두고 각 스케줄링의 텀을 가방으로 둔다면 각 작업을 수행하는데 있어서 최대 이익을 구할 수 있을 것이다.

이렇게 Python과 Java로 백준의 "보석 도둑" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊