📌 출처
📝 문제
수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.
김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.
참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)
수강신청 대충한 게 찔리면, 선생님을 도와드리자!
⌨ 입력
첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)
이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)
🖨 출력
강의실의 개수를 출력하라.
💻 내 코드
1. 리스트를 사용하여 구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
Lecture[] lectures = new Lecture[N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
lectures[i] = new Lecture(start, end);
}
Arrays.sort(lectures, (e1, e2) -> (e1.start == e2.start ? e1.end - e2.end : e1.start - e2.start));
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(lectures[0].end);
for(int i = 1; i < lectures.length; i++) {
if(pq.peek() <= lectures[i].start) {
pq.poll();
pq.add(lectures[i].end);
} else {
pq.add(lectures[i].end);
}
}
System.out.println(pq.size());
}
static class Lecture {
int start;
int end;
Lecture(int start, int end) {
this.start = start;
this.end = end;
}
}
}✏ 설명
이렇게 예제가 몇 개 없는 문제가 가장 어려운 것 같다..
예제는 통과를 해도 막상 제출하면 틀렸다느니, 시간 초과라느니 온갖 것들이 난무하니ㅠㅠ
이번 문제의 핵심은 시간 초과 였다.
처음 내가 접근한 방식은 맞았다.
- 내가 접근한 방식
- 우선 입력받는 순서대로 진행한다.
- 종료 시각을 리스트에 집어넣는다.(강의실을 새로 배정한다)
- 만약 리스트에 있는 시간들 중에 시작 시간보다 작거나 같은 시간이 있으면 그 시간을 뺀다.(강의실을 새로 배정하지 않는다.)
이렇게 접근을 했는데 내가 간과한 한 가지..
시작 시간이 오름 차순으로 주어지지 않는다.
이게 무슨 말이냐면 만약 시작 시간이 오름 차순으로 주어지면 내가 생각한 방법으로 풀 수 있다(물론 시간 초과는 뜨지만)
하지만 오름 차순으로 주어지지 않을 경우를 생각해보자.
- 4 ~ 5 / 1 ~ 3 / 5 ~ 6
- 이렇게 세 개의 시간표가 주어졌다고 해보자.
- 그럼 우선 순서대로 진행되니까 4~5 에서 5가 리스트에 들어간다.
- 그 다음 1~3을 볼건데 종료시간은 3이고 리스트에 있는 시간 중 시작시간인 1보다 작거나 같은 시간이 없다.
- 따라서 강의실을 새로 배정받게 된다.
- 1~3 수업을 먼저 하고 4~5 수업을 하면 되는데!!
그래서 우선 입력받은 숫자들을 시작 시간을 기준으로 오름차순으로 정렬했다.
만약 시작 시간이 같으면 끝나는 시간을 기준으로 오름차순으로 정렬했다.
그리고 이제 똑같이 리스트에 집어넣고 시작 시간과 비교를 하면 되는데 내가 하던 대로 하면 시간 초과가 발생한다.
그래서 사용한 우선순위 큐!!
이 방법을 사용하면 리스트에 있는 모든 숫자들을 비교할 필요 없이 가장 앞에 있는 숫자랑만 비교를 하면 된다.
왜냐면 그게 제일 빨리 끝나는 시간이니까.
그리디 알고리즘은 이상하게 어렵다.
정해진 방식이 없어서 그런걸까.
많이 풀어봐야 할 것 같다.
