[그리디] 코딩테스트 문제 TIL (강의실 배정) - 백준 11000번

말하는 감자·2024년 12월 25일

TIL algorithm baekjoon greedy heap priority queue python sorting 그리디 백준 알고리즘 우선순위 큐 정렬 코딩테스트 코딩테스트 준비 파이썬 힙

코딩테스트 유형별 풀이

목록 보기

46/67

1. 오늘의 학습 키워드

그리디
우선순위 큐
힙

2. 문제: 11000. 강의실 배정

단계: 🥇 골드 5단계
주제:
출처: https://www.acmicpc.net/problem/11000

문제

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

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

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

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

입력

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

이후 N개의 줄에 $S_i, T_i$ 가 주어진다. ( $0 ≤ S_i < T_i ≤ 10^9$ )

출력

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

예제 입력 1 복사

예제 출력 1 복사

3. 문제 풀이

Step1. 문제 이해하기

이 문제의 핵심은 최소한의 강의실 개수로 모든 수업을 배정하는 것입니다.

수업은 시작 시간( $S_i$ )과 종료 시간( $T_i$ )이 주어지며, 하나의 강의실에서는 동시에 두 개 이상의 수업이 진행될 수 없습니다. 단, 수업이 끝난 직후( $T_i \leq S_j$ )에 다른 수업을 시작하는 것은 가능합니다.

입출력을 살펴보도록 하겠습니다.

Input:
- 첫 번째 줄에는 수업의 개수 N이 주어집니다. N은 1이상 2 * $10^5$
- 다음 N개의 줄에는 각 수업의 시작 시간과 종료 시간이 주어집니다.
Output: 모든 수업을 배정하는 데 필요한 최소 강의실의 수를 출력합니다.

Step2. 문제 분석하기

이 문제는 최소한의 강의실 개수를 구해야 하는 문제입니다. 그렇다면 어떻게 해야 해결할 수 있을까요?

우선, 강의 시작 시간이 가장 빠른 강의가 강의실 1개를 먼저 차지해야 합니다. 그 다음은 해당 강의가 끝나는 시간과 가장 가깝게 시작하는 다른 강의실이 있다면 이것은 첫 강의가 사용했던 강의실을 사용할 수 있습니다.

따라서, 강의 시작 시간 순으로 정렬을 진행해야 한다는 것을 알 수 있습니다. 또한, 강의실을 재활용하기 위해 종료 시간 체크가 필요합니다. 따라서 우선순위 큐를 활용하여 종료 시간이 빠른 강의를 관리할 수 있습니다.

정리해보자면 다음과 같습니다.

정렬:
- 먼저, 수업을 시작 시간( $S_i$ ) 기준으로 오름차순 정렬합니다. 이렇게 하면 시작 시간이 빠른 수업부터 차례대로 확인할 수 있습니다.
우선순위 큐 사용:
- 각 강의실에서 진행 중인 수업의 종료 시간( $T_i$ )만을 큐에 저장합니다.
- 새로 확인하는 수업의 시작 시간( $S_i$ )이 큐에서 가장 작은 종료 시간(가장 빨리 끝나는 수업)보다 크거나 같으면, 강의실을 재사용할 수 있으므로 큐에서 제거합니다.
- 새로 배정된 수업의 종료 시간을 큐에 추가합니다.
결과:
- 큐에 남아 있는 종료 시간의 개수가 필요한 강의실의 최소 개수입니다.

Step3. 코드 설계

정렬:
- 강의 시작 시간이 빠른 순서대로 정렬합니다. 시작 시간이 같다면 종료 시간 기준으로 정렬됩니다.
- 이를 통해, 시간 순서대로 강의를 배정할 수 있습니다.
우선순위 큐로 종료 시간 관리:
- 현재 진행 중인 강의들의 종료 시간을 우선순위 큐(heap)로 관리합니다.
- 새 강의를 추가할 때:
  - 가장 먼저 끝나는 강의의 종료 시간(heap의 최솟값)과 비교.
  - 새 강의의 시작 시간이 종료 시간보다 크거나 같다면, 해당 강의실을 재사용 가능합니다(큐에서 제거).
  - 재사용이 불가능하다면 새로운 강의실을 추가합니다.

최소 강의실 개수 계산:
- 우선순위 큐의 크기는 현재 진행 중인 강의의 개수이며, 이는 동시에 사용 중인 강의실의 개수와 동일합니다.
- 모든 강의를 처리한 뒤, 큐의 최대 크기를 출력합니다.

Step4. 코드 구현하기

import sys
from heapq import heappush, heappop
N = int(sys.stdin.readline().strip())
classes = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def sol(classes):
    classes.sort()
    heap = []
    for start, end in classes:
        if heap and heap[0] <= start:
            heappop(heap)
        heappush(heap, end)
    return len(heap)
print(sol(classes=classes))

시간 복잡도:
1. 정렬:
  - 강의를 시작 시간 기준으로 정렬합니다.
  - 시간 복잡도: $O(N \log N)$ .
2. 우선순위 큐:
  - 각 강의에 대해 heappop()과 heappush() 연산이 이루어집니다.
  - 각 연산의 시간 복잡도: $O(\log M)$ , 여기서 $M$ 은 현재 큐의 크기.
  - 최악의 경우, $M = N$ 이므로 $O(N \log N)$ .
  
  전체 시간 복잡도:
- 정렬 $O(N \log N)$ + 힙 관리 $O(N \log N)$ = $O(N \log N)$ .
결과: