[백준] 1202번 보석 도둑 문제에 필요한 자료구조는? (PriorityQueue사용)
1. 문제
1) 링크
문제는 위의 링크를 클릭하면 확인할 수 있다.
2. 풀이
이 문제를 풀기 위해서 우리는 class를 하나 만들어 주는 것이 필요하다. 왜냐하면 보석과 가방을 묶어서 하나의 객체로 만들 것이고, 필요한 인스턴스는 무게, 가격, 그리고 보석인지 가방인지를 알려주는 정수 이렇게 세개이기 때문이다. 가방의 경우 가격은 주어져 있지 않기 때문에 0이라고 가정하고, 보석일 경우 0, 가방일 경우 1로 instance를 만들어 객체를 만들어주기로 했다.
다시 말해서,
class Jewelry implements Comparable<Jewelry>{
int m,v,t;
Jewelry(int m, int v, int t){
this.m=m; //무게
this.v=v; //가격
this.t=t;//t가 0이면 보석, 1이면 가방
}
public int compareTo(Jewelry a){
if (this.m!=a.m){
return this.m-a.m;
}
else{
return this.t-a.t; //가방이 나중에 오도록
}
}
}위와 같이 class를 하나 만들어준다. 그런 다음에 우리가 해당 객체를 정렬할 때 필요한 compareTo 메서드를 구현해줄 필요가 있다. 우선 무게 순으로 정렬을 할 것이기 때문에 m을 기준으로 오름차순이 될 수 있도록 정렬을 해주고, 만약 무게가 같을 경우에 보석이 다 온 뒤에 가방이 올수 있도록 t를 기준으로 정렬해주었다. t는 가방일 경우에 1이고, 보석일 경우에 0으로 해놓았기 때문에 this.t-a.t를 하게 되면 같은 무게일 경우 보석 뒤에 가방이 오게 된다.
그렇다면 정렬을 한 뒤의 모습은 어떠할지 생각해보자.
ex) 보석: (무게, 가격) 순으로 (3, 100) , (1, 50), (2, 99) 가 있었다고 가정하고,
가방: (무게) 2, 4 인 무게를 담을 수 있는 가방 두개가 있다고 가정하면,
정렬 이후에는
(1, 50), (2, 99), 무게 2인 가방, (3, 100), 무게 4인 가방
이렇게 정렬이 된다는 것을 알 수 있다.
즉, 무게 2인 가방에 담을 수 있는 것은 정렬된 배열 기준으로 무게 2인 가방 앞에 오는 보석들이고, 무게 4인 가방에 담을 수 있는 보석들도 마찬가지로, 해당 가방 앞에 정렬된 보석들이라는 것을 알 수 있다.
그 중에서 우리는 최대 가격의 보석을 담을 수록 좋기 때문에 가장 가격이 높은 보석을 담아야 한다.
3. 자료구조 - PriorityQueue
그러면 이것을 구현할 수 있는 유용한 자료구조로 무엇을 사용하면 좋을까?
PriorityQueue를 사용해서 구현을 해보았다. PriorityQueue를 사용한 이유는 담는 순서대로 담기는 일반 Queue와는 달리, 순서대로 정렬이 될 수 있기 때문이다.
그러면 우리는 가방이 나오기 전까지 보석의 가격을 PriorityQueue에다가 담아주면 된다. 하지만 가장 높은 가격의 가방이 가장 처음에 오도록 담고 싶기 때문에, 가방의 무게에 -1을 곱한 값을 PriorityQueue에 담아주어야 한다.
만약 -1을 곱하지 않는다면 숫자는 오름차순 정렬이 기본이기 때문에 가장 처음의 숫자는 가장 낮은 가격의 가방이 오게 된다. 우리가 원하지 않았던 결과이기 때문에 음수를 곱해준 것이다.
이렇게 한 뒤에, 만약 가방이 나온다면, 우리는 PriorityQueue에 있는 보석 한개를 꺼내주게 되면 그것이 가방에 담을 수 있는 가장 비싼 보석이 되는 것이다. (정렬을 이미 해 놓았기 때문에)
4. 코드
이 모든 것을 구현한 코드는 아래와 같다.
import java.util.*;
class Jewelry implements Comparable<Jewelry>{
int m,v,t;//t가 0이면 보석, 1이면 가방
Jewelry(int m, int v, int t){
this.m=m;
this.v=v;
this.t=t;
}
public int compareTo(Jewelry a){
if (this.m!=a.m){
return this.m-a.m;
}
else{
return this.t-a.t; //가방이 나중에 오도록
}
}
}
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int k=sc.nextInt();
Jewelry [] jew=new Jewelry[n+k];
for(int i=0; i<n; i++){
int m=sc.nextInt();
int v=sc.nextInt();
jew[i]=new Jewelry(m,v,0);
}
for(int i=0; i<k; i++){
int m=sc.nextInt();
jew[n+i]=new Jewelry(m, 0, 1);
}
Arrays.sort(jew);
PriorityQueue<Integer>q=new PriorityQueue<>();
long ans=0;
for(Jewelry j: jew){
if (j.t==0){
//보석일 경우
q.offer(-j.v);
}
else{
if (!q.isEmpty()){
ans+=(long)q.poll()*-1;
}
}
}
System.out.println(ans);
}
}