백준 11000 강의실 배정 Python 3

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

11000번: 강의실 배정

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ11000.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
import heapq
def get_lecture_rooms(N, lectures):
    rooms = list()
    heapq.heappush(rooms, lectures[0][1])
    for i in range(1, N):
        if rooms[0] <= lectures[i][0]:
            heapq.heappop(rooms)
        heapq.heappush(rooms, lectures[i][1])
    print(len(rooms))

input = sys.stdin.readline
N = int(input())
lectures = list()
for _ in range(N):
    lectures.append(list(map(int, input().split())))
lectures.sort()
get_lecture_rooms(N, lectures)

---

풀이 과정

N개의 수업을 모두 배치하는데 최소의 강의실을 사용해야 한다.

이때, 강의실의 이전 강의가 끝난 시간 이후에 시작하는 강의인 경우 같은 강의실에 배치할 수 있다.

반대로 이전 강의가 끝난 시간보다 전에 시작하는 강의인 경우는 다른 강의실에 배치해야 한다.

 

따라서, 모든 강의를 시작시간 기준으로 오름차순 정렬한 후에 이전 강의가 가장 빨리 끝난 강의실의 종료 시간과 비교해서 강의실을 새로 개설해야할지 아니면 기존 강의실을 이용할 건지를 판단하면 된다.

강의들이 시작시간 기준으로 오름차순 정렬할 것이고, 모든 강의를 배치해야하기 때문에 가장 이전 강의가 빨리 끝난 강의실만 비교하면 된다.

따라서, 이전 강의가 끝난 시각이 가장 빠른 강의실을 매번 뽑아내기 위해서 MinHeap을 이용한다.

heap에 노드를 추가/삭제 할때마다 힙 구조를 재정비 해야하고 이때 소요되는 시간복잡도는 O(n log2 n)이다.

import sys
import heapq
def get_lecture_rooms(N, lectures):
	#강의실들의 직전 강의 종료시간을 담는 리스트
    rooms = list()
    #rooms을 heap으로 만들어주고 가장 빨리 시작하는 강의의 종료시간을 담아 초기화
    heapq.heappush(rooms, lectures[0][1])
    
    for i in range(1, N):
    	#i번째 강의의 시작시간이 가장 빨리 끝난 강의실의 종료시간 이후인 경우, 해당 강의를 같은 강의실에서 진행할 수 있다
        if rooms[0] <= lectures[i][0]:
        	#강의실의 종료시간을 i번째 강의의 종료시간으로 바꿔주기 위해 root 노드를 삭제한다
            heapq.heappop(rooms)
            
        #현재 강의의 종료시간을 힙에 추가한다
        #if 조건에 맞는 경우에는 전체 강의실 개수는 그대로이며, 아니라면 새 강의실이 추가된다
        heapq.heappush(rooms, lectures[i][1])
        
    print(len(rooms))

input = sys.stdin.readline
N = int(input())
lectures = list()
for _ in range(N):
    lectures.append(list(map(int, input().split())))

#강의 시작시간을 기준으로 오름차순 정렬
lectures.sort()
get_lecture_rooms(N, lectures)

#시간복잡도 = O(nlogn), 공간복잡도 = O(n)

---

오답 노트

처음 문제를 풀 때, 강의들을 시작 시간과 끝나는 시간을 기준으로 정렬한 후, 첫 강의가 끝나는 시간을 강의실로 배정했다.

이후 강의를 탐색하면서 강의실의 끝나는 시간들을 모두 탐색하며 기존 강의실에 이어서 강의를 이어갈지 말지를 탐색했다.

그 결과 시간초과가 났다.

그 이유는 강의 수 N이 최대 200,000이기 때문에 최악의 경우로 강의실이 200,000개라면 시간 복잡도가 O(N^2)이 되기 때문이다.

시작 시간을 기준으로 오름차순 정렬을 하고 강의실 중에 강의가 끝나는 시간이 가장 빠른 강의실에 배치 할 수 있는 지 아닌지만 판단하면 훨씬 효율적인 알고리즘을 짤 수 있다.

import sys
def get_lecture_rooms(N, lectures):
    rooms = [lectures[0][1]]
    for i in range(1, N):
        for j in range(len(rooms)):
            if lectures[i][0] >= rooms[j]:
                rooms[j] = lectures[i][1]
                break
        else:
            rooms.append(lectures[i][1])
    print(len(rooms))

input = sys.stdin.readline
N = int(input())
lectures = list()
for _ in range(N):
    lectures.append(list(map(int, input().split())))
lectures.sort(key=lambda x: (x[0], x[1]))
get_lecture_rooms(N, lectures)