[백준(BOJ)] #11000- 강의실 배정 (파이썬, Python3)

문제

 

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

11000번: 강의실 배정

 

---

문제 풀이

 

이 문제는 그리디 알고리즘과 우선순위 큐를 이용해서 해결할 수 있습니다.

 

2022.07.18 - [알고리즘/개념] - [파이썬으로 배우는 알고리즘] 그리디(Greedy) 알고리즘

[파이썬으로 배우는 알고리즘] 그리디(Greedy) 알고리즘

 

2022.07.19 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 우선순위 큐(Priority Queue), 힙(Heap)

[파이썬으로 배우는 자료구조] 우선순위 큐(Priority Queue), 힙(Heap)

 

수업의 시작시간이 어떤 수업의 종료시간보다 같거나 늦으면 그 수업의 강의실에서 이어서 수업이 가능하다는 점을 잘 생각해서 풀어야 합니다.

 

1) 입력받은 수업의 리스트를 시작 시간을 기준으로 오름차순 정렬

2) 제일 첫 번째로 시작하는 수업의 종료시간을 우선순위 큐(최소힙)에 삽입

3) 다음으로 빨리 시작하는 수업의 시작시간을 우선순위 큐에서 제일 앞에 있는 값과 비교(제일 앞에 있으면 종료시간이 제일 빠른 수업!)

4) 우선순위 큐에 있는 종료시간이 비교하는 수업의 시작 시간보다 늦으면 그 수업의 종료시간을 우선순위 큐에 삽입(강의실 한 개 더 배정)

5) 우선순위 큐에 있는 종료시간이 비교하는 수업의 시작 시간보다 빠르면 큐에서 삭제하고 그 수업의 종료시간을 우선순위 큐에 삽입(강의실 이어서 사용)

6) 위 작업을 마지막 수업까지 반복하면 우선순위 큐에 남아있는 종료시간의 개수가 강의실 개수가 됨 

 

이해를 쉽게 하기 위해서 그림으로 그려 설명을 해보겠습니다.

 

1) 수업 시작 시간을 기준으로 오름차순 정렬

 

2) 제일 빨리 시작하는 수업 1의 종료 시간을 우선순위 큐에 삽입

 

3) 다음으로 빨리 시작하는 수업 2의 시작 시간 2는 수업 1의 종료시간인 3보다 작으므로 강의실이 한 개 더 필요함. 수업 2의 종료 시간을 우선순위 큐에 삽입

 

4) 다음으로 빨리 시작하는 수업 3의 시작 시간 3은 수업 1의 종료시간 3이랑 같으므로 강의실을 이어서 사용할 수 있음. 수업 1의 종료시간을 삭제하고 수업 3의 종료시간을 우선순위 큐에 삽입

 

결국 우선순위 큐에 남은 종료시간의 수 즉, 우선순위 큐의 크기가 강의실 개수가 됨

 

---

구현

코드

import sys
import heapq
input = sys.stdin.readline

if __name__ == "__main__":
    n = int(input())
    schedule_list = [list(map(int, input().split())) for _ in range(n)]
    schedule_list.sort()

    pq = list()
    # 종료시간 저장
    heapq.heappush(pq, schedule_list[0][1])

    for i in range(1, n):
        if schedule_list[i][0] >= pq[0]:
            heapq.heappop(pq)
        heapq.heappush(pq, schedule_list[i][1])

    print(len(pq))

결과