[백준 11000] 강의실 배정- python (solved.ac - 골드 5)

 

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

11000번: 강의실 배정

풀이

문제를 보았을때 알수있는 힌트

문제 자체는 참 간단하게 나와있는데 알고있어야 할 것들이 꽤 있어야 풀 수 있는 문제였다.

먼저 우선순위 큐를 알고있어야 풀수있는 문제이다. 문제를 보면 수업이 끝난 직후 이어서 다음 수업을 시작한다고하는데 이것이 우선적인 순서를 하고 이어서 계속 진행 되기에 우선 순위 큐를 이용해야한다.

python에서는  heapq 라이브러리를 알고 있어야 빨리 해결할 수 있는 문제이다.

heapq를 통해 데이터를 넣으면 정렬이 되어서 우선적인 순서를 먼저 처리할 수 있다. 

 

문제를 통해 최소의 강의실을 찾는 문제이기에 room을 강의실로 하여 현재 강의실에 수업시간이 겹치는지 확인하여 방을 늘리면 된다.

예를 들어  1 4, 2 3, 3 5 (시작 시간) (끝 시간)의 시간이 수업 시간이 있을때 첫수업을 room에 넣는다.

room에는 끝나는 시간만을 넣으면 된다. room=[4]이라고 들어갈것이고 이어서 2번째 수업인 2시 시작을 room의 첫 배열과 비교하면 2시 시작이 불가능하다.

 이때 강의실을 추가해준다. 이러면 room에 3이 들어가진다 이때 heapq로 인해 정렬이 되는데 [4,3]이 아닌 room=[3,4]로 들어가지게 된다. 

이어서 3시 수업을 확인했을때 room의 첫 배열인 3이기에 이어서 수업을 진행하면된다. 이때 heapq에서 pop을 통해 3을 꺼내고 3시 수업의 끝시간을 넣어준다. 이러면 room은 [4,5]가 된다.

이때 room의 길이(len)이 답이 된다.

 

import sys
import heapq

input = sys.stdin.readline

n = int(input())
n_list=[]
room = [] 
for _ in range(n):
    s,t=map(int, input().split())
    n_list.append([s,t])
n_list.sort()

heapq.heappush(room,n_list[0][1])

for i in range(1,n):
    if n_list[i][0]<room[0]:
        heapq.heappush(room,n_list[i][1])
    else:
        heapq.heappop(room)
        heapq.heappush(room,n_list[i][1])

print(len(room))

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon11000.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리