[백준/그리디] 11000: 강의실 배정 - 파이썬

문제

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

11000번: 강의실 배정

 

한 3~4시간 고민하고도 도저히 답이 안나와서 힌트를 얻었다.

https://www.youtube.com/watch?v=7noZLdfHIMQ&t=918s&ab_channel=Chan-SuShin 

다음과 같이 알고리즘을 작성하였다.

1. 각 강의의 시작시간, 끝나는 시간을 배열에 입력한다.
2. 강의의 시간이 입력되어 있는 배열을 시작시간 순으로 오름차순 정렬한다.
3. 가장 빠르게 시작하는 강의 끝나는 시간을 힙에 넣는다. (힙=강의실)
4. 배열의 두번째 강의의 시작시간 이랑 첫 번째 힙에 입력된 시간(첫번째 강의가 끝나는 시간)과 비교한다
5. 만약 두번째 강의 시작시간이 힙의 첫번째 원소의 키값 즉, 강의의 끝나는 시간보다 더 빠르게 시작한다면(두번째 강의시작시간 < 첫번째 힙에 들어있는 강의의 끝나는 시간)
6. 힙에 원소를 넣고(강의실) 그 원소에 두번째 강의 시간(키)을 입력함
7. 만약 두번째 강의의 시작시간이 첫번째 강의 끝나는 시간보다 늦다면 힙(강의실에)에 저장된 첫번째 끝나는 시간을 제거하고 두번째 강의의 끝나는 시간을 집어넣음
8. 4~7과정을 반복하면 여러개의 힙의 원소들이 생성되는데 원소의 수가 이 문제에서 구하려고 하는 강의실의 갯수임.

설명이 매끄럽지 못하다.. 그림자료를 추가할 예정이다.

 

테스트 케이스 입력

6

1 3

2 5

7 8

4 12

9 10

7 11

출력: 3

 

제출 답안

import heapq
import sys

def inputdata(n):
    classarr = []
    for _ in range(n):
        a,b = list(map(int, sys.stdin.readline().split()))
        classarr.append([a,b])
    classarr.sort(key = lambda x:x[0])
    return classarr
    
def solution(): 
    n = int(sys.stdin.readline())
    classarr = inputdata(n)
    roomAmount = []
    heapq.heappush(roomAmount, classarr[0][1])
    
    for i in range(1, n):
        if classarr[i][0] < roomAmount[0]:
            heapq.heappush(roomAmount , classarr[i][1])
        else:
            heapq.heappop(roomAmount)
            heapq.heappush(roomAmount, classarr[i][1])
            
    return len(roomAmount)

print(solution())