[Baekjoon] 16692_Greedy Scheduler

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

---

< Greedy Scheduler >

 

문제 풀이 

 

PriorityQueue를 사용하여 계산이 빨리 끝나는 곳을 찾는다.

 

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 _16692_ { // Greedy Scheduler

	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 c = 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 o1[0] - o2[0];
			}
		});

		int idx = 1;
		int result[] = new int[c];

		st = new StringTokenizer(bf.readLine());
		for (int i = 0; i < c; i++) {
			if (idx <= n) {
				queue.add(new int[] { Integer.parseInt(st.nextToken()), idx++, i });
			} else {
				int info[] = queue.poll();
				result[info[2]] = info[1];
				queue.add(new int[] { info[0] + Integer.parseInt(st.nextToken()), info[1], i });
			}
		}

		while (!queue.isEmpty()) {
			int info[] = queue.poll();
			result[info[2]] = info[1];
		}

		for (int i = 0; i < c; i++) {
			bw.write(result[i] + " ");
		}
		bw.flush();
	}
}

변수)
n, c : 계산원 수, 고객 수
queue : PriorityQueue <int [시간, 계산대 번호, 입력 순서]>
idx : 계산대 번호
result : 고객의 장바구니를 처리할 계산원 번호

 

계산원 수 n과 고객 수 c를 입력받는다. c만큼 고객의 장바구니를 처리하는 데 걸리는 시간을 입력받으며 다음 과정을 거친다.

 

1) 아직 비어있는 계산대가 있다면 가장 적은 숫자를 가진 계산원에게 배정

2) 계산대가 비어있지 않다면 queue.poll을 한 후 그 계산대 위치에 배정

 

PriorityQueue가 빌 때까지 poll 한 후 계산대 번호를 result 배열에 저장한다. 최종 result 배열을 출력한다.

---

---