백준 #11000 - 강의실 배정
문제
수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.
김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.
참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)
수강신청 대충한 게 찔리면, 선생님을 도와드리자!
입력
첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)
이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)
출력
강의실의 개수를 출력하라.
예제 입력
3
1 3
2 4
3 5
예제 출력
2
강의의 시작시간과 끝시간이 주어지고, 모든 수업이 가능한 최소한의 강의실 개수를 찾는 문제이다.
자료구조를 공부했을 때 그림으로 수없이 많이 그렸던 문제... 코드로는 처음 풀어봤다는 사실...
import sys
input = sys.stdin.readline
n = int(input())
times = []
rooms = []
for i in range(n):
time = list(map(int, input().split()))
times.append(time)
times = sorted(times, key = lambda x: x[0])
for time in times:
if len(rooms) > 0:
for i in range(len(rooms)):
if rooms[i] <= time[0]:
rooms[i] = time[1]
break
else: rooms.append(time[1])
elif len(rooms) == 0:
rooms.append(time[1])
print(len(rooms))
내가 처음에 작성한 코드이다.
강의 시간을 담은 times 리스트는 시작 시간 기준으로 정렬하고, 하나씩 순회하며 조건에 따라 판단한다.
rooms 리스트에는 강의실 별 끝나는 시간을 저장하여 len(rooms)가 곧 강의실 개수이다.
만일 rooms 리스트에 해당 강의 시작 시간보다 작은 숫자가 있다면 해당 room 값을 갱신하고,
만일 rooms 리스트가 비어있거나 강의 시작 시간보다 모두 큰 숫자라면 새로운 room 값을 append한다.
로직 상으로는 문제가 없었고, 실행 결과도 옳게 나왔지만 시간초과가 떴다...
각 강의 시간마다 모든 강의실을 확인하기 때문에 이중 반복문으로 시간 복잡도가 증가한 것이다.
그래서 우선순위 큐(힙)을 사용해야 했다.
import sys
import heapq
input = sys.stdin.readline
n = int(input())
times = []
rooms = []
for i in range(n):
time = list(map(int, input().split()))
times.append(time)
times = sorted(times, key = lambda x: (x[0], x[1]))
rooms.append(times[0][1])
for i in range(1, n):
if rooms[0] <= times[i][0]:
heapq.heappop(rooms)
heapq.heappush(rooms, times[i][1])
print(len(rooms))
여기서 heapq.heappop()은 힙에서 가장 작은 값을 제거하고 반환하는 함수이다.
우선순위 큐에서 가장 우선순위가 높은 항복을 제거한다.
heapq.heappush()는 힙에 새로운 요소를 추가하는 함수이다.
힙 속성을 유지하기 위해 올바른 위치에 삽입한다.
위 두 함수 모두 O(logn)의 시간복잡도를 가진다.
코드를 보면, 시간초과가 난 기존 코드와 로직은 같다.
rooms[0]은 가장 빨리 끝나는 강의실의 끝나는 시간을 나타낸다.
만일 rooms[0]가 해당 강의 시작 시간보다 작다면, heapq.heappop()을 통해 가장 빨리 끝나는 강의실 시간을 제거한 후 새로 추가한다.
만일 rooms[0]가 해당 강의 시작 시간보다 크다면, 제거 없이 새로 추가만 진행한다.
힙은 완전 이진트리를 기본으로 하는데, 이는 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안되었다.
힙에서는 가장 높은 (혹은 가장 낮은) 우선순위를 가지는 노드가 항상 루트에 오기 때문에 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.
파이썬 heapq 모듈은 최소 힙의 형태로 정렬된다.
즉, 가장 작은 값이 언제나 인덱스 0인 이진 트리의 루트에 위치하는 것이다.
그렇기에 heapq.heappop()을 하면 가장 작은 값이 리턴되고, heapq.heappush()를 하면 알맞은 위치에 원소를 추가해준다.
두 함수 모두 O(logn)의 시간복잡도!
빈 리스트를 생성한 후 heapq의 함수 인자로 넘기면 힙 구조로 다룰 수 있다.
이미 원소가 들어있는 리스트를 힙으로 만들려면
from heapq import heapify 후
heapify(heap_list) 형식으로 함싸주면 된다.
시간복잡도는 O(n)이다.