문제

풀이

1차 시도

풀이 방법

보석 배열은 무게가 낮 - > 높 으로 정렬함
배낭 배열은 용량이 낮 -> 높 으로 정렬
PriorityQueue 생성해서 해당 하는 가방에 들어올 수 있는 보석을 pq 에 넣고
가장 앞에 있는 요소를 뽑아서 ret변수에 누적으로 더해줌

pq는 가격 순으로 정렬하고 가격이 같으면 무게가 낮은 순으로 정렬

코드

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

public class Main {
	static class jewel implements Comparable<jewel>{
		int weight, value;
		jewel(int weight, int value){
			this.weight = weight;
			this.value = value;
		}

		@Override
		public String toString() {
			return "jewel [weight=" + weight + ", value=" + value + "]";
		}

		@Override
		public int compareTo(jewel o) {
			if(this.value == o.value) {
				return this.weight - o.weight;
			}
			return o.value - this.value ;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n, k;
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		jewel [] arr = new jewel[n];
		for(int i = 0; i<n;i++) {
			st = new StringTokenizer(br.readLine());
			arr[i] = new jewel(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
		}
//		for(int i =0; i < n; i++) {
//			System.out.println(arr[i].toString());
//		}
		
		int [] bag = new int[k];
		for(int i =0; i < k; i++) {
			bag[i] = Integer.parseInt(br.readLine());
		}
		
		// 보석을 무게에 따라 오름차순으로 정렬
        Arrays.sort(arr, (o1, o2) -> o1.weight - o2.weight);
        
//		for(int i =0; i < n; i++) {
//			System.out.println(arr[i].toString());
//		}
		Arrays.sort(bag);
//		for(int i = 0;i < k;i++) {
//			System.out.println(bag[i]);
//		}
		
		////////// input 다 받음
		long ret = 0;
		int j = 0;
		int c = 0;
		for(int i =0; i < k; i++) {
			PriorityQueue<jewel> possible = new PriorityQueue<>(); //가방에 들 어 갈수있는 애들 넣을 큐
			c = j;
			while(c<n) {
				if(bag[i] >= arr[c].weight) {
					possible.add(new jewel(arr[i].weight, arr[i].value));
				}
				c++;
				if(!possible.isEmpty()) {
					ret +=  possible.poll().value;;
					j+=1;
					break;
				}
			}
		}
		System.out.println(ret);
	}
}

결과

틀렸습니다.
디버그를 찍어보니 중복되는 값이 들어와서 틀렸었다.
=> 중복되는 값이 안 들어 오게 수정

2차 시도(최종)

풀이 방법

1차 풀이 방법에서
문제 였던 중복 됬던 값이 안 들어 오게 하기 위해
class에 idx 값을 넣어놔서 중복 되는 값이 안 들어 오게 했다

코드

package BOJ;

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

// 풀이 방법: 

public class BOJ1202_보석도둑 {
	static class jewel implements Comparable<jewel>{
		int weight, value, idx;
		jewel(int weight, int value, int idx){
			this.weight = weight;
			this.value = value;
			this.idx = idx;
		}

		@Override
		public String toString() {
			return "jewel [weight=" + weight + ", value=" + value + "]";
		}

		@Override
		public int compareTo(jewel o) { // 가격 높은 순으로 정렬 가격이 같으면 무게가 낮은 순으로 정렬
			if(this.value == o.value) {
				return this.weight - o.weight;
			}
			return o.value - this.value ;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n, k;
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		jewel [] arr = new jewel[n];
		for(int i = 0; i<n;i++) {
			st = new StringTokenizer(br.readLine());
			arr[i] = new jewel(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()),i);
		}
//		for(int i =0; i < n; i++) {
//			System.out.println(arr[i].toString());
//		}
		
		int [] bag = new int[k];
		for(int i =0; i < k; i++) {
			bag[i] = Integer.parseInt(br.readLine());
		}
		
		// 보석을 무게에 따라 오름차순으로 정렬
        Arrays.sort(arr, (o1, o2) -> o1.weight - o2.weight); // 이거 안 하고 그냥 정렬 쓰니까 compare에 정의된 정렬 방법이 사용 됨
        
//		for(int i =0; i < n; i++) {
//			System.out.println(arr[i].toString());
//		}
		Arrays.sort(bag);
//		for(int i = 0;i < k;i++) {
//			System.out.println(bag[i]);
//		}
		
		////////// input 다 받음
		long ret = 0;
		boolean [] select = new boolean[n]; // 선택 된거 판별 하기 위한 배열
        PriorityQueue<jewel> possible = new PriorityQueue<>(); // 해당 가방에 들어 갈 수 있는 값 을 넣어 주기 위한 pq 생성
        int j = 0; // arr 배열의 인덱스
        for(int i = 0; i < k; i++) {
            while(j < n && arr[j].weight <= bag[i]) {
                if (!select[arr[j].idx]) { // 이미 사용되지 않은 보석만 추가
                    possible.add(arr[j]);
                }
                j++;
            }
            while (!possible.isEmpty()) {
                jewel temp = possible.poll();
                if (!select[temp.idx]) { // 선택된 보석이 이미 사용되지 않았다면
                    select[temp.idx] = true; // 사용됨 으로 변경
                    ret += temp.value;
                    break; 
                }
            }
        }
        System.out.println(ret);
    }
}

회고

그리디 알고리즘이였고

		@Override
		public int compareTo(jewel o) {
			if(this.value == o.value) {
				return this.weight - o.weight;
			}
			return o.value - this.value ;
		}
	}

를 만들어 놓고
Arrays.sort를 사용 하니 자동으로 저 비교방법이 사용 되었다.

그래서

   Arrays.sort(arr, (o1, o2) -> o1.weight - o2.weight);

익명 함수를 만들어 jewel 배열을 정렬 할 때는 이 방법을 사용했다.