[BOJ-1202][그리디] 보석 도둑 -Java

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

1202번: 보석 도둑

package algo;

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

public class boj_1202_보석도둑 {
	static int n,k;
	static Jewelry jewelryInfo[];
	static int []bag;
	static class Jewelry implements Comparable<Jewelry>{
		int m;
		int v;
		public Jewelry(int m, int v) {
			this.m = m;
			this.v = v;
		}
		@Override
		public int compareTo(Jewelry o) {
			if(this.m==o.m) return o.v-this.v; //무게 같으면 무게 내림차순
			return this.m-o.m;
		}
		
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		long result=0;
		n=Integer.parseInt(st.nextToken());
		k=Integer.parseInt(st.nextToken());
		jewelryInfo=new Jewelry[n];
		bag=new int[k];		
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			jewelryInfo[i]=new Jewelry(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}
		
		for(int i=0; i<k; i++) {
			bag[i]=Integer.parseInt(br.readLine());
		}
		
		Arrays.sort(jewelryInfo);
		Arrays.sort(bag);
		
		result=solve();
		System.out.println(result);
	}
	private static long solve() {
		long result=0;
		int j=0;
		
		PriorityQueue<Integer> pq=new PriorityQueue<>(Collections.reverseOrder());//value 내림차순
		for(int i=0; i<k; i++) { //가방만큼 돈다 
			while(true) {//j부터 시작해서 현재 가방의 크기보다크면 break
				if(j>=n || jewelryInfo[j].m>bag[i]) break; //현재 가방크기보다 무거우면 break;
				pq.add(jewelryInfo[j++].v);
			}
			
			if(!pq.isEmpty()) {
				result+=pq.poll();
			}
		}
		
		return result;
	}

}

소요시간 : 50분

 

런타임에러를 잡느라 시간이 많이 소요되었습니다ㅜ

 

우선 N,K의 제한사항이 1<N,K<=300,000 이기 때문에

O(N*K)으로는 풀 수가 없습니다.

그래서 O(n long n)복잡도를 먼저 생각하고 그리디로 접근하였습니다.

 

 

우선 로직을 살펴보면

 

1. 보석을 무게순으로 오름차순정렬한다. ( 무게가 같다면 가치가 높은 순으로)

2. 가방을 무게순으로 오름차순정렬한다.

 

3. 현재 가방에 담을 수 있는 무게보다 작거나 같은 보석들을 우선순위 큐에 넣습니다(내림차순)

4. 현재 가방에 담을 수 있는 가장 큰 가치를 poll해서 무게에 더해줍니다.

 

끝~