[백준/Java] 1202번 보석 도둑

 

문제 풀이

시간 초과에 주의해야하며 PriorityQueue로 풀었다.

처음엔 이중 for문을 돌려 시간초과가 났다.

 

BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());

int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());

int[][] arr = new int[N][2];

for(int i=0; i<N; i++) {
    st = new StringTokenizer(bf.readLine());
    arr[i][0] = Integer.parseInt(st.nextToken());
    arr[i][1] = Integer.parseInt(st.nextToken());
}

1. 보석의 개수 N과 가지고 있는 가방 K를 입력 받는다.

이차원 배열 arr를 생성하고, 크기는 N행 2열로 초기화한다.

 

보석의 개수 N번만큼 반복하며

보석의 정보(무게, 가격)을 입력받아 arr에 대입한다.

 

Arrays.sort(arr, (o1, o2) -> {
    return o1[0] - o2[0];
});

2. 보석의 무게를 기준으로 오름차순 정렬한다.

 

ArrayList<Integer> weight = new ArrayList<Integer>();
for(int k=0; k<K; k++) {
    weight.add(Integer.parseInt(bf.readLine()));
}

Collections.sort(weight);

3. 가지고 있는 가방에 담을 수 있는 무게를 저장하기 위해 arrayList인 weight를 생성하고 입력 받는다.

그리고 오름차순으로 정렬해준다.

 

PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());

4. 우선순위큐를 생성하고, 정렬 조건은 내림차순으로 한다.

 

int idx = 0;
long ans = 0;
for(int w : weight) {
    while(idx < N && arr[idx][0] <= w) {
        pq.add(arr[idx][1]);
        idx++;
    }

    if(!pq.isEmpty()) {
        ans += pq.poll();
    }
}

5. idx는 보석의 idx를 의미하고,

ans는 정답을 담기 위한 변수다.

 

가방이 수용할 수 있는 무게에 대해 반복문을 돌리고,

그 무게보다 같거나 작은 보석들이 있다면 우선순위 큐에 넣는다.

 

while문을 빠져나왔다면,

우선순위 큐가 비어있는지 확인하고, 비어있지 않다면 우선순위 큐에서 값을 하나 꺼낸다.

우선순위 큐는 내림차순으로 정렬되어있기 때문에 수용 가능한 보석 중 값어치가 가장 비싼 보석을 꺼낸 것이다.

 

System.out.println(ans);

6. 정답을 출력한다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		int[][] arr = new int[N][2];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(bf.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}
		
		ArrayList<Integer> weight = new ArrayList<Integer>();
		for(int k=0; k<K; k++) {
			weight.add(Integer.parseInt(bf.readLine()));
		}
		
		Collections.sort(weight);
		
		Arrays.sort(arr, (o1, o2) -> {
			return o1[0] - o2[0];
		});
		
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
		
		int idx = 0;
		long ans = 0;
		for(int w : weight) {
			while(idx < N && arr[idx][0] <= w) {
				pq.add(arr[idx][1]);
				idx++;
			}
			
			if(!pq.isEmpty()) {
				ans += pq.poll();
			}
		}
		System.out.println(ans);
	}
}

 

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