[백준] 1202번 : 보석 도둑 - JAVA [자바]

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

---

그리디 알고리즘과 우선순위 큐를 사용해서 풀었다.

가장 작은 가방부터 가장 값어치가 큰 보석을 넣는다는 생각을 가지고 풀어보자.

우선 가장 작은 가방부터 탐색해야 하므로 가방을 무게를 기준삼아 오름차순으로 정렬한다.

Arrays.sort(bag);

또한, 가방을 탐색하며 보석을 볼때 가장 가벼운 보석부터 보면서 넣을 수 있는지 판단하기 위해 보석 배열도 무게를 기준삼아 오름차순으로 정렬하고 무게가 같을 경우 값어치가 더 큰 것을 앞에 배치하여 정렬한다.

Arrays.sort(jewels, (o1, o2) -> {
	// 무게가 같을 경우 값이 더 높은 것부터 정렬
    if (o1.weight - o2.weight == 0) {
    	return o2.cost - o1.cost;
	}

	return o1.weight - o2.weight;
});

우선 순위 큐에서는 가장 값어치가 높은 보석부터 꺼내기 위해 규칙을 세워준다. 또한, 값어치가 같을 경우 무게가 가벼운 것부터 정렬한다.

Queue<jewel> queue = new PriorityQueue<>((o1, o2) -> {
	if (o2.cost - o1.cost == 0) {
    	return o1.weight - o2.weight;
	}
    return o2.cost - o1.cost;
});

알고리즘을 살펴보자.

// 범위를 보아 정답은 long 타입으로 정의해야 한다.
long answer = 0;
// 무게가 작은 가방부터 살핀다.
for (int k = 0, i = 0; k < K; k++) {
	// 현재 가방에 넣을 수 있는 보석들을 큐에 삽입한다.
	while (i < N && jewels[i].weight <= bag[k]) {
    	queue.add(jewels[i]);
        // 다음 가방을 탐색할때는
        // 이 이후의 보석부터 보면 되므로
        // (현재 보석까지는 다음 가방보다 작은 현재 가방에 들어가므로 
        // 다음 가방에는 무조건 들어갈 수 있으므로 건너뛴다)
        i++;
	}
    // 현재 가방에 들어갈 수 있는 보석이 있을 경우
    if (!queue.isEmpty()) {
    	// 가장 값어치가 큰 보석을 큐에서 빼서 정답에 더해준다.
    	answer += queue.poll().cost;
	}
}

---

public class bj1202 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] split = br.readLine().split(" ");
        int N = Integer.parseInt(split[0]);
        int K = Integer.parseInt(split[1]);

        jewel[] jewels = new jewel[N];
        int[] bag = new int[K];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            String[] split1 = line.split(" ");
            jewels[i] = new jewel(Integer.parseInt(split1[0]), Integer.parseInt(split1[1]));
        }

        for (int i = 0; i < K; i++) {
            bag[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(bag);
        Arrays.sort(jewels, (o1, o2) -> {
            // 무게가 같을 경우 값이 더 높은 것부터 정렬
            if (o1.weight - o2.weight == 0) {
                return o2.cost - o1.cost;
            }

            return o1.weight - o2.weight;
        });

        Queue<jewel> queue = new PriorityQueue<>((o1, o2) -> {
            if (o2.cost - o1.cost == 0) {
                return o1.weight - o2.weight;
            }
            return o2.cost - o1.cost;
        });

        long answer = 0;
        for (int k = 0, i = 0; k < K; k++) {
            while (i < N && jewels[i].weight <= bag[k]) {
                queue.add(jewels[i]);
                // 이제 다음 보석부터 보면 되므로
                i++;
            }
            if (!queue.isEmpty()) {
                answer += queue.poll().cost;
            }
        }

        System.out.println(answer);
        br.close();
    }

    public static class jewel {
        int weight;
        int cost;

        public jewel(int weight, int cost) {
            this.weight = weight;
            this.cost = cost;
        }
    }
}