[백준] 보석 도둑 1202번 - Java
풀이 참조
나의 풀이
class Jewel {
int mass;
int value;
Jewel(int mass, int value) {
this.mass = mass;
this.value = value;
}
}
public class JewelThief {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
Jewel[] jewels = new Jewel[N];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int mass = Integer.parseInt(st.nextToken());
int value = Integer.parseInt(st.nextToken());
jewels[i] = new Jewel(mass, value);
}
Arrays.sort(jewels, new Comparator<Jewel>() {
@Override
public int compare(Jewel o1, Jewel o2) {
if(o1.mass == o2.mass) {
return (o2.value - o1.value);
}
return o1.mass - o2.mass;
}
});
int[] bags = new int[K];
for(int i = 0; i < K; i++) {
bags[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(bags);
PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
long result = 0;
for(int i = 0, idx = 0; i < K; i++) {
while(idx < N && jewels[idx].mass <= bags[i]) {
queue.offer(jewels[idx++].value);
}
if(!queue.isEmpty()) {
result += queue.poll();
}
}
bw.write(result + "\n");
bw.flush();
bw.close();
br.close();
}
}
- 우선 혼자 해결하지 못하고 블로그를 참조하여 코드를 작성하였다.
- 일반적인 접근 방법으로 계산하면 시간 초과로 풀 수 없다. 우선 큐를 통해서 접근해야한다.
- 우선 입력받은 보석의 무게를 기준으로 오름차순, 만약 보석의 무게가 같다면 보석의 가격을 기준으로 내림차순을 해줘야 한다. 정렬을 하기 쉽도록 Jewel객체를 만들어서 new Comparator로 정렬을 해주었다.
- 그리고 가방의 무게를 입력받고 가방의 무게도 오름차순으로 정렬을 한다.
- 이제 우선 큐를 생성해준다. 단, 우선 큐의 기본 값은 오름차순 즉, 값이 작은 것 먼저 리턴을 해준다. 떄문에 Comparator.reverseOrder()를 사용해서 값이 큰 것부터 반환하도록 설정을 해준다.
- 이제 정렬된 인덱스가 N보다 작고, 보석의 무게가 배낭의 무게보다 작거나 같은동안 배낭에 큐에 보석의 가격들을 넣어준다.
- 이렇게 while문 반복이 끝난 후, 큐기 비어있지 않다면, 값을 꺼내와 answer에 더해준다. 이 때 큐는 Comparator.reverseOrder 상태이기 때문에 큐가 가지고 있는 가장 큰 값을 반환해준다.
느낀점
for(int i = 0, idx = 0; i < K; i++) {
while(idx < N && jewels[idx].mass <= bags[i]) {
queue.offer(jewels[idx++].value);
}
우선 이 부분에서 메모리 초과가 나왔었다. 처음에는 idx를 밖으로 빼서 int idx = 0; 으로 정의를 했더니 그게 문제였다. 때문에 idx를 저렇게 for문 안에 정의하고 나서는 메모리 초과 없이 통과되었다.
PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
우선 큐를 이런 식으로 우선순위를 설정할 수 있다는 것을 알았다. 앞으로 써먹을 일이 많을 듯 하다.
Author And Source
이 문제에 관하여([백준] 보석 도둑 1202번 - Java), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@goshk95/백준-보석-도둑-1202번-Java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)