[BaekJoon] 11000 강의실 배정 (Java)

🔗 문제 링크

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

📝 문제 설명

해당 문제는 Input값으로 주어지는 모든 강의를 할 때 필요한 강의실의 최솟값을 구하는 문제이다.

1. 문제를 풀기 위해서는 먼저 강의를 시작시간을 기준으로 정렬을 해줘야한다. (시작 시간이 같을 경우 끝나는 시간이 빠른게 앞으로 오게 정렬)

2. 강의를 정렬 후에는 for문을 통해 강의를 하나씩 순회하며 가장 빨리 끝나는 강의의 종료 시간과 새로운 강의의 시작 시간을 비교하며 새로운 강의실이 필요한가에 대한 유무를 확인해줍니다.

   가장 빨리 종료되는 강의실은 강의가 종료되는 시간을 저장하는 Priority를 생성하여 가장 빨리 끝나는 강의의 시간을 peek()를 통해 확인할 수 있도록 구현하였습니다.

3. 가장 빨리 끝나는 강의가 새로운 강의 시작시간 이후에 끝나는 경우 PriorityQueue에 새로운 강의의 종료시간을 추가해주며(강의실 추가), 새로운 강의시간 이전에 끝나는 경우 poll()을 통해 현재 강의를 Queue에서 빼내고 새로운 강의를 추가해줍니다.

4. 최종적으로 PriorityQueue의 size가 필요한 강의실의 수가 됩니다.

👨🏻‍💻 작성한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		ArrayList<Lecture> lecList = new ArrayList<>();
		PriorityQueue<Integer> roomList = new PriorityQueue<>();
		StringTokenizer st;
		
		for (int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			
			lecList.add(new Lecture(start, end));
		}
		Collections.sort(lecList);
		
		
		for (Lecture l: lecList) {
			if (roomList.isEmpty()) { // 강의실이 없으면 추가
				roomList.add(l.end);
				continue;
			}
			
			// 다음 강의가 시작하는 시간 이전에 
			// 강의가 끝나는 강의실이 있으면 해당 강의실에서 강의 시작
			if (roomList.peek() <= l.start) {
				roomList.poll();
			}
			roomList.add(l.end);
		}
		
		System.out.println(roomList.size());
	
	}
	
	static class Lecture implements Comparable<Lecture>{
		int start;
		int end;
		public Lecture(int start, int end) {
			this.start = start;
			this.end = end;
		}
		
		@Override
		public int compareTo(Lecture o) {
			if (this.start == o.start) return this.end < o.end ? -1:1;
			return this.start < o.start? -1:1;
		}
	}

}