오답노트 #1202 : 보석 도둑

풀이방법 및 문제점

2022.04.30

예제에 대해서는 모두 올바른 값이 출력되지만, 시간 초과가 발생하여 실패하였다.

내가 짠 알고리즘의 시간복잡도가 O(NK)이기 때문이다.

 

알고리즘은 다음과 같다.

 

보석을 가치 기준으로 내림차순 정렬하되, 가치가 같은 보석끼리는 무게를 기준으로 오름차순 정렬한다.

가방의 용량은 오름차순 정렬한다.

 

가벼운 가방부터 순서대로 살핀다.

가장 앞에 있는 보석부터 살피며, 이 가방에 들어갈 만큼 가벼운지 확인한다. 들어갈 수 있으면 그 보석을 가방에 집어넣으면 된다. 아까 가치 기준으로 내림차순 정렬을 해뒀기 때문이다.

 

이렇게 모든 가방을 살피면 된다.

 

그러나 보석들 중 가장 가치가 낮은 보석만이 가방에 들어갈 수 있을 정도로 가볍다면 최악의 시간복잡도에 해당하게 된다...

 

최적의 보석을 찾는 부분이 이중 for문이라 시간복잡도가 O(NK)다. 줄여야 할 것 같다.

더 빠른 정렬 방식을 찾을 수도 있겠는데 이건 큰 효과가 있을지 모르겠다.

우선순위 큐를 써야만 하는 건가??

 

코드

Java(2022.04.30)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		//보석 정보를 저장할 Jewel 객체 배열
		Jewel[] jewels = new Jewel[n];
		
		//보석 정보 읽어오기
		for(int i = 0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			jewels[i] = new Jewel(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}
		
		//가치가 높은 순으로, 가치가 같다면 무게가 가벼운 순으로 정렬
		Arrays.sort(jewels, new Comparator<Jewel>() {

			@Override
			public int compare(Jewel j1, Jewel j2) {
				// TODO Auto-generated method stub
				int m1 = j1.m;
				int m2 = j2.m;
				int v1 = j1.v;
				int v2 = j2.v;
				
				//먼저 가치를 비교
				if(v1<v2) return 1;
				else if(v1 == v2) {
					//가치가 같으면 무게 비교
					if(m1>m2) return 1;
					else return -1;
				}
				else return -1;
			}
			
		});
		
		//가방 정보 읽어오기
		int[] bags = new int[k];
		for(int i = 0; i<k; i++) {
			bags[i] = Integer.parseInt(br.readLine());
		}
		
		//가방을 무게를 기준으로 오름차순 정렬
		Arrays.sort(bags);
		
		//각 가방에 보석을 넣을 수 있는지 점검
		int sum = 0;	//지금까지 가방에 넣은 보석의 가치
		//최대한 작은 가방에 최대한 비싼 보석부터 넣으려 해보기
		//모든 가방이 찰 때까지 반복
		for(int i = 0; i<k; i++) {
			int cur = bags[i];	//이번 가방의 용량
			
			for(int j = 0; j<n; j++) {
				
				//이번 보석을 이번 가방에 넣을 수 있는 경우
				if(cur >= jewels[j].m) {
					//전체 보석 가치에 반영하고
					sum += jewels[j].v;
					//해당 보석 객체의 무게를 1000001로 설정(중복해서 담지 않도록)
					jewels[j].m = 1000001;					
					break;	//가방에 보석 하나만 넣을 수 있으므로 반복문 종료
				}
				//이번 보석이 너무 무거운 경우 아무것도 하지 않고 넘어감
			}
		}
		
		//정답 출력
		System.out.print(sum);

	}

}

//보석 클래스
class Jewel {
	int m;	//무게
	int v;	//가치
	public Jewel(int m, int v) {
		this.m = m;
		this.v = v;
	}
}