[BOJ] 백준 11000 - 강의실 배정 풀이

1. 문제

https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

2. 풀이

• 생각보다 굉장히 어려웠던 문제였다.
• 이 문제의 핵심은 "현재 탐색중인 수업의 시작 시간이 다음 수업 시작 시간보다 작거나 같으면 같은 강의실을 배정할 수 있다" 이다.
• 주요 자료 구조
  1. PriorityQueue<Integer> pq : 배정한 수업이 들어가있는 우선순위 큐
  2. List<Lesson> lessonList : 수업 리스트
• 우선 수업을 리스트에 넣고 수업 시작 시간을 기준으로 오름 차순 정렬하고 수업 시작 시간이 같다면 종료 시간을 기준으로 오름 차순 정렬한다.
• 처음 수업을 꺼내어 일단 우선 순위 큐에 넣는다.
• 그 후 다음 수업부터 마지막 수업까지 돌면서 다음과 같은 로직을 수행한다.
  • 강의실의 수를 최소로 하기 위해서는 여러 수업을 같은 강의실에 최대한 배정해야 한다.
  • 하나의 강의실은 하나의 수업이 끝나고 다음 수업을 배정할 수 있다.
  • 따라서 "다음 수업의 시작 시간" >= "현재 배정한 수업 중 종료 시간이 가장 빠른 수업" 이라면 같은 강의실을 사용할 수 있다. 이렇다면 우선 순위 큐에서 하나를 Poll() 한다. 왜냐하면 우선 순위 큐의 사이즈가 곧 강의실의 수이기 때문에 우선 순위 큐에 들어있는 시작 시간이 가장 빠른 수업을 하나 Poll() 하고 현재 수업을 넣으면 하나의 강의실에 2개의 수업을 배정한 것과 같은 효과를 낼 수 있다.
  • 그리고 큐에 현재 수업을 넣어준다.
    
    
    

3. 소스 코드

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


public class Main {
	// 수업이 끝나는 시간을 기준으로 우선순위 큐를 이용하여 정렬한다.
	// 현재 보고 있는 수업의 시작 시간 <= 다음의 수업 시작 시간 이면 강의실을 배정할 수 있다.
	
	static class Lesson {
		int start;
		int end;
		public Lesson(int start, int end) {
			this.start = start;
			this.end = end;
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// pq : 배정한 수업이 들어가 있는 pq. 이 pq의 사이즈가 곧 강의실의 갯수이다.
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		
		// 수업 리스트
		List<Lesson> lessonList = new ArrayList<>();
		
		int N = Integer.parseInt(br.readLine()); // 수업 수
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			lessonList.add(new Lesson(start, end));
		}
		
		// 수업 리스트를 정렬한다.
		Collections.sort(lessonList, new Comparator<Lesson>() {
			@Override
			public int compare(Lesson o1, Lesson o2) {
				if (o1.start == o2.start) {
					return o1.end - o2.end;
				}
				
				return o1.start - o2.start;
			}
		});
		
		// 처음 수업을 일단 배정한다.
		pq.add(lessonList.get(0).end);
		for (int i = 1; i < lessonList.size(); i++) {
			// (다음 수업의 시작 시간 >= 현재 배정한 수업 중 종료 시간이 가장 빠른 수업 )이 참이라면
			// 이는 같은 강의실을 사용할 수 있기 때문에 그 수업을 꺼낸다.
			if (pq.peek() <= lessonList.get(i).start) {
				pq.poll();
			}
			
			// pq에 add 한다는 것은 수업을 넣는다는 것이고 이는 강의실을 새로 배정하는 것과 같다.
			pq.add(lessonList.get(i).end);
		}
		
		bw.write(Integer.toString(pq.size()));
		bw.flush();
		bw.close();
		br.close();
	}
}

4. 점수

50 / 100