[Baekjoon] 25101_Robin Hood

문제(출처: https://www.acmicpc.net/problem/25101)

---

< Robin Hood >

 

문제 풀이 

 

우선순위 큐를 사용하여 가장 부유한 사람에게서 100을 뺀다.

 

my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class _25101_ { // Robin Hood

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				if (o1[0] == o2[0]) {
					return o1[1] - o2[1];
				}
				return o2[0] - o1[0];
			}
		});

		st = new StringTokenizer(bf.readLine());
		for (int i = 0; i < n; i++) {
			queue.add(new int[] { Integer.parseInt(st.nextToken()), i });
		}

		boolean flag = false;
		for (int i = 0; i < k; i++) {
			if (queue.peek()[0] <= 100) {
				flag = true;
				break;
			}
			int temp[] = queue.poll();
			temp[0] -= 100;
			queue.add(temp);
		}

		if (flag) {
			bw.write("impossible");
		} else {
			int result[] = new int[n];
			while (!queue.isEmpty()) {
				int temp[] = queue.poll();
				result[temp[1]] = temp[0];
			}
			for (int i = 0; i < n; i++) {
				bw.write(result[i] + " ");
			}
		}
		bw.flush();
	}
}

변수)
n, k : 사람 수, 수행해야 할 절도의 수 
queue : 우선순위 큐 
flag : 수행 여부 
result : 남아 있는 총 재산 

 

사람 수와 수행해야 할 절도의 수를 입력받는다. 우선순위 큐를 선언하여 재산이 많은 순으로, 재산이 같다면 목록에서 앞에 있는 사람 순으로 정렬한다. 사람 수만큼 재산을 입력받아 우선순위 큐에 저장한다. 수행해야 할 절도의 수만큼 우선순위큐를 살펴보며 100보다 클 때 poll 하여 100을 뺀 후 다시 우선순위 큐에 저장한다. 100 이하라면 절도를 수행할 수 없으므로 종료한다. 

 

최종 flag 값이 true라면 "impossible"을 출력하고, false라면 우선순위 큐에 있는 모든 값을 poll 하여 배열에 목록 순으로 저장한 뒤 배열을 출력한다. 

---

---