[Baekjoon] 1379_강의실 2

Gold III

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

---

< 강의실 2 >

 

문제 풀이 

 

우선순위 큐 2개를 사용해서 문제를 해결했다.

우선순위 큐 a에는 [강의 시작 시간, 강의 끝나는 시간, 강의 번호] 배열을 저장해서 우선순위를 강의 시작시간이 빠른 순으로, 시작 시간이 같다면 끝나는 시간이 빠른 순으로 정렬했다.

다른 우선순위 큐 b에는 [강의 끝나는 시간, 강의실 번호]를 저장해서 우선순위를 강의 끝나는 시간이 빠른 순으로, 강의실 번호가 작은 순으로 정렬했다.

 

a의 값을 순서대로 b에 저장하는데, b의 젤 앞에 값의 강의 끝나는 시간보다 a에서의 강의 시작 시간이 같거나 크다면 b의 맨 앞의 강의가 끝난 후에 그 강의실을 사용할 수 있다는 뜻이므로 b의 값을 poll 한 후 저장해 준다.

 

이때, 그 강의 번호를 index로 하는 배열에 강의실 번호를 저장해 준다.

 

 

 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 _1379_ { // 강의실 2

	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());

		int result[] = new int[n + 1];

		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());
			int num = Integer.parseInt(st.nextToken());
			queue.add(new int[] { Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), num });
		}

		PriorityQueue<int[]> room = 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 lecture[] = queue.poll();
		room.add(new int[] { lecture[1], 1 });
		result[lecture[2]] = 1;

		int idx = -1;
		while (!queue.isEmpty()) {
			lecture = queue.poll();
			idx = -1;
			if (room.peek()[0] <= lecture[0]) {
				int temp[] = room.poll();
				idx = temp[1];
			}
			if (idx == -1) {
				idx = room.size() + 1;
			}
			result[lecture[2]]=idx;
			room.add(new int[] { lecture[1], idx });
		}

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

 

Main

변수)
n : 강의 수
result : 각 강의에 배정할 강의실 번호
queue: 우선순위 큐 [강의 시작 시간, 강의 끝난 시간, 강의 번호]
room: 우선순위 큐 [강의 끝난 시간, 강의실 번호] 

 

- 강의 수(n) 입력

- 강의 수만큼 입력받아 우선순위 큐 queue에 저장

- room 우선순위 큐에 queue 값을 뽑아 먼저 강의실 하나 저장

- queue 가 빌 때까지 반복

: room 우선순위 큐의 젤 첫 번째 값이 들어갈 값 보다 작거나 같다면 강의가 끝난 후 다음 강의를 시작할 수 있다는 뜻이므로 poll 후 추가

: poll 했다면 그 강의실에 들어가야 하므로 강의실 번호로 저장 But 새로운 강의실이라면 강의실 번호로 room의 size+1을 저장

- 강의실 개수와 각 강의에 배정할 강의실 번호를 순서대로 출력

 

---

---