[Baekjoon] 1374_강의실

Gold V

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

---

< 강의실 >

 

문제 풀이 

 

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

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

다른 우선순위 큐에는 강의 끝나는 시간을 저장한다. 이때, 이 우선순위 큐 젤 앞에 있는 값이 새로 들어오는 값 보다 작거나 같다면 강의가 끝난 후 다음 회의를 시작할 수 있는 것이므로 poll해준 후 넣어준다.

 

 

 my solution (Java)

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

public class _1374_ { // 강의실

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		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());
			st.nextToken();
			queue.add(new int[] { Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()) });
		}

		PriorityQueue<Integer> room = new PriorityQueue<>();
		room.add(queue.poll()[1]);

		while (!queue.isEmpty()) {
			int time[] = queue.poll();
			if (room.peek() <= time[0]) {
				room.poll();
			}
			room.add(time[1]);
		}
		System.out.println(room.size());
	}
}

 

Main

변수)
n : 강의 수
queue: 우선순위 큐 [강의 시작 시간, 강의 끝난 시간]
room: 우선순위 큐 [강의 끝난 시간] 

 

- 강의 수(n) 입력

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

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

- queue 가 빌 때까지 반복

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

- 강의실 개수는 room의 size이므로 room size 출력

 

---

---