백준 1202 / 보석 도둑 / 그리디, 우선순위 큐 / JAVA
오늘 살펴볼 문제는 백준 1202번 <보석 도둑> 문제이다.
https://www.acmicpc.net/problem/1202
1202번: 보석 도둑
문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 �
www.acmicpc.net
이 문제는 전형적인 그리디 알고리즘 문제이다. 각각의 주머니에 대해서 넣을 수 있는 최대 가격의 보석을 적절하게 넣어주면 풀 수 있는 문제이다.
처음에 내가 했던 접근은 다음과 같다.
보석을 1. 가격이 비싼 순으로 2. 같은 가격이면 무게가 가벼운 순으로 정렬되는 PriortyQueue를 만든다. 그리고 가방을 무게 순으로 오름차순으로 정렬한다. 그리고 첫 번째 가방부터 PQ를 돌면서 들어갈 수 있는 가장 비싼 보석을 담는다. 그렇게 전체 가방에 대한 for문을 돌리며 모든 가방에 각각에 들어갈 수 있는 제일 비싼 보석을 담는다.
하지만 이렇게 알고리즘을 짜게 되면 O(NK)가 나오는데 N = 300,000, K = 300,000이어서 시간초과가 나온다. 따라서 나는 시간복잡도를 더 낮추는 방법을 찾아야 했다.
고민도 하고 다른 분들의 풀이도 참고하면서 시간 복잡도를 O(NlogN)으로 낮출 수 있는 방법을 찾아냈다.
먼저 배열 두 개를 만든다. 하나는 보석이 담긴 배열, 그리고 다른 하나는 가방이 담긴 배열이다. 이 두 배열을 만들고 무게를 기준으로 오름차순 정렬을 진행하면 다음과 같다. 여기서 N개의 원소가 담긴 배열을 정렬하기에 NlogN의 시간 복잡도가 사용된다.
그리고 나서 가방 배열을 첫 번째 부터 하나씩 탐색하며 보석을 하나씩 넣어준다. 방법은 가방 배열 하나를 탐색할 때 마다 그 가방의 크기 이하의 무게를 가진 보석을 PriortyQueue에 담고, 해당 pq는 보석 가격을 기준으로 내림차순 되도록 만들었다. 즉 while 문을 돌고 나면, 해당 PQ의 첫 번째 값(pq.poll())이 해당 가방에 넣을 수 있는 가장 비싼 보석이 되는 것이다.
보석이 중복되서 가방에 들어가지 않게 보석을 pq에 담을 때 마다 idx를 하나씩 증가시켜 주고, 이미 가방에 담긴 보석은 pq에서 빼 내주기 때문에 중복해서 담을 수도 없도록 만들어 주면 매 번 가방을 탐색할 때마다 최적의 해를 찾아서 구해줄 수가 있다.
예제에서는 첫 번째 가방에 무게 2의 가격이 99인 보석이 담기고, 두 번째 가방에는 무게 1의 가격이 65인 보석이 담기게 된다. 이 과정에서 발생하는 시간 복잡도는 O(N+K)이고, 결과적으로는 앞선 정렬 과정에서 생기는 O(NlogN)의 시간복잡도로 문제를 해결할 수 있게 된다.
해당 문제에 대한 내 자바 소스코드는 다음과 같다.
그리디 알고리즘을 연습하기 좋은 문제이고, 시간복잡도 관점에서 고민을 한 번 더 해야 풀리는 살짝 까다로운 문제이다. 추천!