[algorithm] 백준 강의실 배정 #11000

해당 블로그는 개인이 공부하고, 정리한 걸 기록하는 공간입니다.
오타, 오류가 존재할 수 있습니다. 댓글을 달아주시면 수정할 수 있도록 하겠습니다.

문제 풀러가기

코드 보기

import heapq, sys

lecture = []

# input  
N = int(sys.stdin.readline())
[heapq.heappush(lecture, list(map(int, sys.stdin.readline().split()))) for i in range(N)]

# 겹치지 않는 강의는 연결 시킨다.      
contract_class = []

while lecture:
    start = heapq.heappop(lecture)
    # 기존에 가장 종료되는 강의 와 새로운 강의가 겹치지 않으면
    # 기존 강의 제거 후 새로운 강의를 삽입한다. (두 개의 강의를 합치는 개념)
    if contract_class and start[0] >= contract_class[0]:
        heapq.heappop(contract_class)
    
    # 기존 강의랑 겹치면 강의를 추가한다.
    heapq.heappush(contract_class, start[1])
            
# 강의의 개수가 최소 강의의 수이다.
print(len(contract_class))

강의실 배정

---

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	2940	873	559	27.978%

문제 설명

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109)

출력

강의실의 개수를 출력하라.

예제 입력 1

3
1 3
2 4
3 5

예제 출력 1

2

설명 & 구현 방법

---

낮은 정답률처럼 까다로운 문제였다.
단순히 풀기가 어려운 문제가 아닌 효율성을 충족해야 하는 문제였다.

처음 풀이는 O(n²) 의 시간 복잡도가 나왔다.
N은 200,000까지 범위이므로 4백억까지 숫자가 올라갔다.
문제에서 제시해준 1초 안에 결과가 나오지 않아 시간 초과가 떴다.
답은 아니지만 처음 풀이를 적어보겠다.

1. [S, T] 배열을 [T, S] 순으로 바꾼 뒤 정렬했다. ( 종료 시간 순 )
2. 가장 빨리 종료된 강의 기준으로 모든 배열을 순회하면서 강의의 시작 시간이 기준이 되는 강의의 종료 시간 보다 빠르면 count 했다.
3. 모든 배열의 count 값을 구한 뒤 가장 큰 값을 반환했다.

이 방식으로 처음에 구현한 뒤 안되서 생각해보니 Nlogn까지 줄여야 할 것 같았다.
왜냐하면, 최초에 정렬은 필수적이라고 생각했는데, 정렬은 아무리 빨라도 Nlogn보다 빠르게 정렬할 수 없기 때문이다.
이후 구현한 방식을 적어보겠다.
최소한의 강의실을 최소한의 교수님 수라고 생각을 했고, 교수님이 최소한으로 되기 위해선 한 교수님이 최대한 많은 강의를 하루종일 맡아야 한다고 생각했다.

1. [S, T] 순으로 정렬한다.
2. 가장 빠른 강의를 꺼낸 뒤 교수님에게 배정한다. (T 시간만 저장)
   1. 만약 교수님이 없다면 그냥 교수님에게 배정한다.
   2. 교수님들이 존재한다면, 가장 빨리 강의가 끝나는 교수님에게 강의를 배정해본다.
      1. 교수님이 맡을 수 없는 강의(겹치는 강의)인 경우 새로운 교수님에게 해당 강의를 배정한다.
      2. 교수님이 맡을 수 있는 강의인 경우 해당 교수님의 강의 끝나는 시간을 해당 강의의 종료 시간으로 update 한다.
3. 모든 강의가 배정될 때까지 반복한 뒤 배정이 끝난 교수님의 수 = 최소 필요 교수님의 수 = 최소 강의실 이 된다.

이 풀이는 모든 강의(N)를 돌면서 가장 강의가 일찍 끝나는 교수님(logn = heap)을 찾아 배정하는 구현이기 때문에 Nlogn의 시간복잡도를 가진다.

다음 부터는 시야를 좀 넓혀서 문제를 풀어야겠다.
알고리즘 실력의 부족도 깨달았다. 알고리즘 공부를 좀 더 열심히 해야겠다.