[JAVA / 백준 : 1202] 보석도둑

조건

가방 하나에는 보석 하나!

가방에 최대 담을 수 있는 무게 중 가장 비싼 보석을 담아야한다. 이미 담은거는 못담음

---

처음 풀때 : 시간초과 ㅜㅜ (보석 개수 * 가방 개수) ..

 

잘못된 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static boolean visited[];
	public static int N, K; //보석 개수, 가방 개수
	public static int[] M, V; // 보석 무게, 보석 가격
	public static long[] C; 	//가방의 최대 무게
	
	public static int findMax(long bag) {
		
		int max = 0;
		int maxIndex = 0;
		for(int i = 0; i < N; i++) {
			if(bag > M[i] && !visited[i]) {
				if(max < V[i]) {
					max = V[i];					
					maxIndex = i;	
				}
			}
		}
		visited[maxIndex] = true;
		return max;
	}
	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt();	//보석 개수
		K = scan.nextInt(); //가방 개수
		M = new int[N];		//보석 무게
		V = new int[N];		//보석 가격
		C = new long[K];	//가방 최대 무게
		
		visited = new boolean[N];
		//visited 함수 false로 바꿔주기 
		Arrays.fill(visited, false);
		
		for(int i = 0; i < N; i++) {
			M[i] = scan.nextInt();
			V[i] = scan.nextInt();
		}
		for(int i = 0; i < K; i++) {
			C[i] = scan.nextLong();
		}
		Arrays.sort(C);
		int sum = 0;
		for(int i = 0; i < K; i++)
		{
			sum += findMax(C[i]);
		}
		System.out.println(sum);
		scan.close();
	}
}

 

1. 보석, 가방을 무게순으로 오름차순으로 정렬

2. 가방을 기준으로 반복문을 돌려, 가방에 넣을 수 있는 보석의 가격을 우선순위 큐에 넣는다.

3. 반복문 한번당 우선순위 큐의 가장 위에 있는 가장 비싼 보석의 가격을 더한다.

 

PriorityQueue는 우선순위 큐로 들어간 값에 우선순위를 매겨서 정렬이 된다. PriorityQueue에 여러 개의 값을 넣을 경우엔 오름차순으로 자동 정렬된다고 생각하면 된다. 출처: https://dundung.tistory.com/88 [DunDung]

PriorityQueue를 내림차순으로 하는 법은 간단하다. 가격을 넣을 때 -1을 곱해주고 넣으면 된다.

그리고 우선순위에서 빼서 더할때 Math.abs()로 절댓값을 더해주면 된다.

큐에서 삽입과 삭제는 O(1)

 

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	public static boolean visited[];
	public static int N, K; //보석 개수, 가방 개수
	public static int[] M, V; // 보석 무게, 보석 가격
	public static long[] C; 	//가방의 최대 무게
	
	public static class Jewelry {
		int weight;
		int value;
		
		public Jewelry(int weight, int value) {
			this.value = value;
			this.weight = weight;
		}

	}
	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt();	//보석 개수
		K = scan.nextInt(); //가방 개수
		PriorityQueue<Integer> pq = new PriorityQueue<>();

        ArrayList<Jewelry> jewelries = new ArrayList<>();
        ArrayList<Integer> bagList = new ArrayList<>();
        for (int i = 0; i < N; i++) 
        	jewelries.add(new Jewelry(scan.nextInt(),scan.nextInt()));
        for (int i = 0; i < K; i++) 
        	bagList.add(scan.nextInt());
		
        //보석점을 오름차순 정렬
        Collections.sort(jewelries, new Comparator<Jewelry>() {
            @Override
            public int compare(Jewelry o1, Jewelry o2) {

                if (o1.weight <= o2.weight) return -1;
                else return 1;

            }
        });
        Collections.sort(bagList);
        
        long answer = 0;
        int idx = 0;//보석점 인덱스

        for (int bag : bagList) {
            //보석점의 길이만큼 반복
            while(idx < N) {
                //가방의 무게가 현재 보석점의 무게보다 크거나 같을 때
                if (bag >= jewelries.get(idx).weight) {
                    //보석점의 가격을 우선순위 큐에 음수 형태로 담는다.(오름차순 정렬이기 때문에)
                    pq.add(-(jewelries.get(idx++).value));
                }else break;
            }
            //결과값에 우선순위 큐에서 가장 큰 값을 뺀다. (가장 작은 값을 절대값 씌우면 가장 큰 값이 된다.)
            if (!pq.isEmpty()) answer += Math.abs(pq.poll());
        }
        System.out.println(answer);
		scan.close();
	}
}