[baekjoon] 백준 11000번(파이썬): 강의실 배정

문제

11000번: 강의실 배정

- 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어진다.

- 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 

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

- 수업 N이 주어진다. (1 ≤ N ≤ 200,000)

- 수업 시작시간과 종료시간 S, T가 주어진다. (1 ≤ S < T ≤ 10^9)

- 모든 수업시간을 가능하게 하는 강의실에 최소 개수를 구하는 문제이다.

알고리즘

- 수업의 개수를 입력받는다. 

- 강의실의 시작시간과 종료시간을 입력받아 리스트 변수에 넣는다.

- 리스트 변수를 시작시간으로 정렬한다.

- 처음 강의실에 종료시간을 강의실에 힙푸시한다.

- 반복문을 통해 모든 강의시간을 확인한다.

- 강의실 종료시간과 다음 수업 시작시간과 비교한다.

- 종료시간이 더 크면 강의실을 하나 더 만들어 다음 수업 종료시간을 힙푸시하여 추가한다.

- 종료시간이 작거나 같으면 현재 강의실 종료시간을 다음 강의 종료시간으로 바꾼다.

- 위 과정을 반복한다.

- 강의실 개수, 즉 리스트의 길이를 출력한다.

코드

import sys
import heapq

n = int(sys.stdin.readline())
heap = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
# 강의 시작시간으로 정렬한다.
heap.sort(key=lambda x: x[0])
# 강의실
room = []
# 처음 강의실에 종료시간
heapq.heappush(room, heap[0][1])

for i in range(1, n):
    # 강의실 종료시간과 다음 강의 시작시간 비교
    if room[0] > heap[i][0]:
        # 강의실 종료시간이 다음 강의 시작시간보다 크면
        # 다른 강의실에 강의를 배정해야 함으로 room 리스트에 다음 강의 종료시간을 힙푸시한다.
        heapq.heappush(room, heap[i][1])
    else:
        # 강의실 종료시간이 다음 강의 시작시간보다 작거나 같으면
        # 강의실에 종료시간을 다음 강의에 종료시간으로 바꿔준다.
        heapq.heappop(room)
        heapq.heappush(room, heap[i][1])

# 강의실 개수 출력
print(len(room))

결과

위 코드에서 반복문 맨 밑에 print(room)을 작성하게 되면 강의실이 어떤 모습으로 추가되는지 다음 출력 화면과 같이 확인할 수 있다.

<출력화면>

위 출력 화면을 보게 되면 처음에 오름차순으로 정렬한 강의에 종료시간인 3이 강의실에 들어간 것을 확인할 수 있다. 그다음 강의에 시작시간인 2와 현재 강의에 종료시간인 3을 비교하여 종료시간이 더 큰 것을 확인하고 강의를 연달아 할 수 없으므로 강의실을 하나 더 만들어 다음 강의에 종료시간인 4를 넣은 것을 확인할 수 있다. 그리고 다음 강의에 시작시간인 3과 현재 강의에 종료시간인 3을 비교하여 종료시간과 같은 것을 확인하고 강의를 연달아 할 수 있으므로 현재 강의에 종료시간을 다음 강의에 종료시간인 5로 바꾼 것을 확인할 수 있다.

따라서 코드를 분석하게 되면 처음에 강의시간을 시작시간으로 정렬하여 정렬한 순서대로 강의실에 종료시간과 비교할 수 있게 했다. 강의실 중에 제일 빨리 종료하는 시간과 다음 강의에 시작시간을 비교하여 종료시간이 더 크면 다른 강의실에 다음 강의에 종료시간을 넣어 새로운 강의실을 만들었다. 그리고 종료시간이 같거나 작다면 강의를 연달아 할 수 있으므로 강의실에 종료시간을 다음 강의에 종료시간으로 바꿔 주었다.

위 문제를 봤을 때 백준의 회의실 문제와 소프티어의 강의실 배정 문제와 비슷한 것을 느낄 수 있다. 다른 점은 두 문제는 필요 없는 회의나 강의를 무시해 한 강의실에 최대의 강의 수를 구하는 문제이고 이번 문제는 필요 없는 강의를 무시하지 않고 필요 없는 강의를 새로운 강의실에 넣어 강의실 각각 최대의 강의를 넣었을 때 강의실의 최소 개수를 구하는 문제인 것이다. 위 문제를 풀어보고 링크에 들어가 문제를 풀어보면 좋을 것 같다.

github

junjange/CodingTest