[Baekjoon] 12764_싸지방에 간 준하

Gold III

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

---

< 싸지방에 간 준하 >

 

문제 풀이 

 

우선순위 큐 2개와 ArrayList, boolean 배열을 사용해서 문제를 해결했다.

 

우선순위 큐 a에는 컴퓨터 이용 시작 시간과 종료 시간을 입력받아 저장하여 우선순위를 이용 시작 시간이 빠른 순으로, 시작 시간이 같다면 종료 시간이 빠른 순으로 정렬했다.

우선순위 큐 b에는 컴퓨터 종료 시간과 컴퓨터 번호를 저장하여 우선순위를 종료 시간이 빠른 순으로, 종료 시간이 같다면 번호가 빠른 순으로 정렬했다.

 

문제에서 비어있는 자리 중에서 번호가 가장 작은 자리에 앉는 것이 규칙이라 했으므로 먼저 다음 사람이 들어왔을 때 종료되는 컴퓨터들을 우선순위 큐 b에서 poll 해준다. 그 후에 비어있는 자리 중에 번호가 가장 작은 곳으로 사람을 보낸다.

 

 

 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.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class _12764_ { // 싸지방에 간 준하

	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;

		int n = Integer.parseInt(bf.readLine());

		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];
			}
		});

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

		PriorityQueue<int[]> computer = 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];
			}
		});
		ArrayList<Integer> result = new ArrayList<>();
		result.add(0);

		boolean check[] = new boolean[n + 1];

		result.add(1);
		check[1] = true;
		computer.add(new int[] { queue.poll()[1], 1 });
		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			int idx = Integer.MAX_VALUE;
			while (!computer.isEmpty() && computer.peek()[0] < temp[0]) {
				check[computer.poll()[1]] = false;
			}
			
			for (int i = 1; i < n + 1; i++) {
				if (!check[i]) {
					idx = i;
					check[idx]=true;
					break;
				}
			}
			
			if (result.size() > idx) {
				result.set(idx, result.get(idx) + 1);
			} else {
				result.add(1);
			}
			computer.add(new int[] { temp[1], idx });
		}

		bw.write(result.size() - 1 + "\n");
		for (int i = 1; i < result.size(); i++) {
			bw.write(result.get(i) + " ");
		}
		bw.flush();
	}
}

 

Main

변수)
n : 사람의 수
queue : 우선순위 큐 [컴퓨터 이용 시작 시간, 컴퓨터 이용 종료 시간] 
computer : 우선순위 큐 [컴퓨터 이용 종료 시간, 컴퓨터 번호]
result : 각 자리를 이용한 사람의 수 저장
check : 자리가 비어있는지 여부

 

- 사람의 수(n) 입력

- 각 사람의 컴퓨터 이용 시작 시각과 종료 시각을 입력받아 우선순위 큐(queue)에 저장

- 우선순위 큐(queue)에 저장된 첫 번째 값을 우선순위 큐(computer)에 저장 및 컴퓨터 첫 번째 자리가 비어있지 않다고 표시(check)와 각 자리를 사용한 사람의 수를 저장하기 위해 result에 값 추가

- queue가 빌 때까지 반복

: 다음 사람의 컴퓨터 시작 시간보다 빨리 끝나는 자리를 찾기 위해 queue에서 뽑아온 시작 시간보다 computer의 첫 번째 값의 끝나는 시간이 빠른 경우 computer에서 poll 해주며 그 자리를 빈자리로 저장 (시작 시간보다 빨리 끝나는 자리가 여러 개 있을 수 있다)

: 컴퓨터 자리를 앞에서부터 탐색하여 빈자리 찾기

: 빈자리가 result의 size보다 작다면 원래 있던 자리가 빈 것이므로 result 값 +1

: 빈자리가 result의 size보다 크다면 새로운 자리란 뜻이므로 result에 값 추가

: computer에 값 추가

- 컴퓨터의 최소 개수와 순서대로 각 자리를 사용한 사람의 수 출력

---

---