1. 문제 링크 및 문제
https://www.acmicpc.net/problem/1374
2. 해결 방법 생각해보자 ...
현재 강의가 끝나는 시간과 다음 강의가 시작하는 시간을 비교하여
다음 강의 시작 시간 >= 현재 강의 끝나는 시간 이라면, 현재 강의실 사용
아니라면, 다른 강의실을 써서 최종적으로 사용한 강의실의 갯수를 계산하면 됩니다.
백준예시 1로 이해해봅시다. 예시를 그대로 가져왔습니다.
- 강의의 시작 시간을 비교할 것이므로 시작 시간순으로 정렬해줍니다.
!!!
여기서부터 설명하는 첫번째 강의,두번째 강의, 세번째 강의 ... 는
강의번호(1,2,3...8)에 따른 순서매김이 아닌 시작시간에 따른 강의입니다.
첫번째 강의 -> 첫째줄 (3,2,14)
두번째 강의 -> 둘째줄(1,3,8)
입니다
!!!
- 첫번째 강의를 시작합니다. 2 시작, 14 끝 -> 강의실 1개
- 두번째 강의를 시작합니다. 3 시작, 8 끝
두번째 강의부터는 이미 사용중인 강의실이 있으니, 이 강의실에 들어갈 수 있는 지 확인 해야합니다.
-> 첫번째로 시작하는 3번 강의가 끝나는 시간과 두번째 강의인 1번 강의의 시작 시간을 비교해서요!
첫번째 강의는 14 에 끝나지만, 두번째 강의는 8에 시작하므로 강의실을 하나 더 사용해야합니다.
-> 강의실 2개
- 세번째 강의 (8번 강의)를 시작합니다. 6 시작, 27 끝
여기서도 사용중인 2개의 강의실과 비교하여, 사용할 수 있다면 강의실을 이어서 사용하도록 합니다.
하지만 6은 14보다 작고, 8보다 작으므로 강의실3 을 사용해야합니다.
💡 여기서 강의실1, 강의실2 둘 다 비교할 필요가 있을까요?
두 강의실 중 먼저 끝나는 시간만 비교해도 되지 않을까요?
왜냐, 먼저 끝나는 강의(8)보다 시작 시간(6)이 빠르다면 당연히 다음 강의실(14)도 사용할 수 없으니까요!
따라서, 여러 강의 중 제일 먼저 끝나는 강의와 비교하여 넣어주면 되기 때문에 Priority Queue를 사용하여 먼저 끝나는 강의가 앞으로 오도록 하여, 제일 먼저 끝나는 강의와 비교해줍니다.
이렇게요! 먼저 끝나는 강의 하나와 비교해줍니다.
8번 강의 6에 시작하므로 강의실2를 이어서 사용할 수 없습니다.
그럼 당연히 강의실2보다 늦게 끝나는 강의실 1은 사용 못하겠죠!
-> 세번째 강의 시작 시, 강의실 3개
- 네번째 강의(강의번호5)를 시작합니다. 시작 6,끝 20 -> 강의실 4 사용
앞의 강의실2 (8끝, 제일 먼저 끝나는 강의) 와 비교했을 때 시작시간(6)이 더 빠르므로
강의실 4 사용, 끝나는 시간순대로 넣어줌.
- 다섯번째 강의(강의번호2)를 시작합니다.. 7시작, 13끝
제일 먼저 끝나는 강의가 8끝 이므로 -> 강의실 5 사용, 끝나는 시간 순으로 넣어줌
- 여섯번째 강의(강의번호4)를 시작합니다.
제일 먼저 끝나는 시간(8)과 현재 강의의 시작 시간(12)을 비교했을 때,
시작 시간이 더 크므로 강의실을 이어서 사용할 수 있습니다!
-> 강의실 2 이어서 사용
이제 이전 강의(강의번호 3) 가 끝나고 시작하는 시간은 더 이상 필요없겠죠?
따라서 강의실 2는 시작12, 끝18이 되고 끝나는 시간 기준으로 강의실에 넣어줍니다.
- 일곱번째 강의(강의번호6)을 시작합니다. 15 시작, 21 끝
제일 먼저 끝나는 강의(13) 보다 시작시간(15)이 크므로 강의실5를 이어서 사용합니다!
강의실 5을 이어서 사용하고, 끝나는 시간순으로 정렬해주면 아래와 같이 됩니다.
- 마지막 강의!(강의번호7)을 시작합니다. 20 끝 25 시작
강의실 1을 이어서 사용하면 되겠죠 !?
따라서 최종적으로
이렇게 5개의 강의실을 사용하게 됩니다.
왼쪽 강의시간은 배열로 표현했구요,
오른쪽 강의실은 우선순위큐에 담아 끝나는 시간과 다음 강의의 시작 시간을 비교하여 코드를 구현했습니다.
코드는 아래와 같습니다.
3. 코드
import java.io.*;
import java.util.*;
class lecture implements Comparable<lecture>{
int start, end ;
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 ;
}else return this.start - o.start ;
}
}
public class Main {
static int N;
static lecture[] lectures;
public static void main(String[] args) throws IOException {
// 값 입력받기 -->
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
lectures = new lecture[N];
StringTokenizer st;
for(int i=0;i<N;i++){
st = new StringTokenizer(br.readLine());
int num = Integer.parseInt(st.nextToken())-1;
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
lectures[num] = new lecture(start, end) ;
}
// <--
Arrays.sort(lectures); // 시작 시간순 정렬
PriorityQueue<Integer> q = new PriorityQueue<>();
for(int i=0;i<N;i++){
q.offer(lectures[i].end); // 현재 강의 넣기
if(q.size() < 1 ) continue ; // 큐가 비어있다면 즉 강의실을 사용중이지 않다면, 비교할 강의실이 없으므로 continue
int endTime = q.peek(); // 제일 먼저 끝나는 시간과
if(lectures[i].start >= endTime) q.poll(); // 다음 강의의 시작시간을 비교
}
System.out.println(q.size());
}
}
