https://www.acmicpc.net/problem/19598
19598번: 최소 회의실 개수
2개 회의실로 3개 회의를 모두 진행할 수 있다. 예를 들어, 첫번째 회의실에서 첫번째 회의를 진행하고 두번째 회의실에서 두번째 회의와 세번째 회의를 진행하면 된다. 1개 회의실로 3개 회의
www.acmicpc.net
전형적인 강의실 문제다.
시작하는 시간과 끝나는 시간이 주어지고 최소의 강의실 개수를 구하는 문제는 매우 흔하게 볼 수 있다.
그러므로 풀는 방법을 마스터 하는 것도 괜찮다고 생각한다.
코딩 문제는 국어 문제가 아니다. 우리가 작가의 의도를 파악할 필요도 없고 왜 이런 문제를 냈을까 이런 생각도 할 필요가 없다. 우리는 단지 기계처럼 필요한 정보만 쏙! 습득해야 한다.
우선 첫째 줄에 회의의 개수가 주어지고 둘째 줄부터 N개의 회의 시작시간과 끝나는 시간이 주어진다.
그리고 출력값으로는 회의실의 개수를 출력한다. 이것만 인지하면 된다.
그러면 코드와 함께 설명하겠다.
|
1
2
3
4
5
6
7
8
9
10
11
|
import sys
import heapq
input = sys.stdin.readline
num = int(input())
lecture,heap = [],[]
num_of_classroom = 1
for _ in range(num):
start,end = map(int,input().split())
lecture.append((start,end))
lecture.sort()
|
cs |
우선 heapq와 sys 모듈을 가져온다.
그 후, 문제에서 주어진대로 수업의 개수를 입력받고 for 반복문을 이용해서 수업의 시작하는 시간과 끝나는 시간을 리스트에 추가시켰습니다. sort함수를 이용해서 시작하는 시간을 기준으로 오름차순으로 정렬했습니다.
*시작하는 시작을 기준으로 오름차순으로 정렬한 이유
-끝나는 시간과 시작하는 시간을 비교해서 강의실을 추가할지 말지 결정하기 때문에 시작하는 시간을 기준으로 정렬합니다.
|
1
2
3
4
5
6
7
8
|
heapq.heappush(heap,lecture[0][1])
for i in range(1,num):
if heap[0] > lecture[i][0]:
heapq.heappush(heap,lecture[i][1])
num_of_classroom += 1
else:
heapq.heappop(heap)
heapq.heappush(heap,lecture[i][1])
|
cs |
그리고 heap에 가장 먼저 시작하는 강의의 종료시간을 추가시킵니다.
1부터 (N-1)까지 반복하는 반복문을 이용해서 가장 작은 종료시간과 i번째 강의의 시작시간을 비교해서 강의 시작시간이 더 크면 i번째 강의의 종료시간을 heap에 최소 힙을 준수하여 추가시키고 강의실의 개수를 하나 추가시킵니다.
만약 강의 종료시간이 더 작다면 가장 작은 종료시간을 heappop 함수를 이용해 추출하고 i번째 강의 종료시간을 heappush을 이용해 heap에 추가시킵니다.
이렇게 하면 최소 강의실 개수를 쉽게 구할 수 있습니다.
백준에서 우선순위 큐 문제를 풀다보면 쉽게 볼 수 있는 문제의 유형입니다. 자주 풀어보시는 걸 추천합니다.
