[Python] 정렬 - 1374.강의실(골5) /heapq를 이용한 시간초과 극복

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

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

1374번: 강의실

---

2. 핵심 아이디어

2-1) 무엇을 고려해야 하나 : 끝나는 시간과 시작시간

 

당신이 4-6시의 강의를 담당하는 교수가 되었다고 하자.

강의실을 예약할 때 우리는 무엇을 고려해야 할까?

 

우리가 강의를 시작하는 4시를 기준으로

다른 강의들의 끝나는 시간을 살펴볼 것이다.

 

만약 어떤 강의실의 강의가 4시 이전에 끝난다면

우리는 그 강의가 끝난 이후에 강의실을 사용할 수 있다. 

 

예를 들어 강의들의 끝나는 시간이 다음과 같다면

 

강의실 예약 현황 : [1시, 5시 ,7시]

=> 안의 요소들은 끝나는 시간

 

우리는 첫번째 강의실을 이용하면 된다.

 

그러나, 만약 모든 강의실의 강의가 4시 이후에 끝난다면

우리는 새로운 강의실을 만들어 강의를 해야한다.

 

예를 들어 강의들의 끝나는 시간이 다음과 같다면

 

강의실 예약 현황 : [5시, 5시 ,7시]

=> 안의 요소들은 끝나는 시간

 

우리는 다음처럼 새로운 강의실에서 강의를 해야한다.

 

강의실 예약 현황 : [5시, 5시 ,6시, 7시]

=> 안의 요소들은 끝나는 시간

 

이렇듯 강의실의 추가 여부는

기존 강의들의 끝나는 시간과

내가 맡은 강의의 시작 시간을 통해 결정난다.

 

2-2) 어떤 순서로 고려해야 하나

 

그럼 어떤 순서로 강의실 추가여부를 고려해야할까?

 

강의 시작 시간이 빠른 순서가 좋겠다. (오름차순)

 

강의 시작시간이 빠른 순서대로

하나씩 강의실 추가여부를 고려할 때엔

 

가장 빨리 끝나는 강의실 시간(오름차순)을 살펴보고 다음과 같이 강의실을 예약하자

가장 빨리 끝나는 시간 < 강의 시작시간이면 -> 지금 강의시간으로 갱신

가장 빨리 끝나는 시간 > 강의 시작시간이면 -> 새로운 강의실 예약

 

예를 들어 A/B교수가 차례대로 강의실을 예약한다고 해보자

A교수 : 4-6시 

B교수 : 4-6시

강의실 예약현황 = [1시, 5시 , 7시]

 

A교수는 4시에 강의를 시작한다.

가장 빨리 끝나는 강의실 시간인 1시와 비교했을 때

시작시간이 더 느리다.

 

따라서 가장 첫번째 강의실의 예약시간을 끝나는 시간으로 갱신하면 된다.

-> 강의실 예약현황 = [6시, 5시 , 7시]

 

이번엔 B교수의 차례다.

B교수도 4시에 강의를 시작한다.

가장 빨리 끝나는 시간인 5시와 비교했을 때

시작시간이 더 빠르다.

 

따라서 B교수가 사용할 수 있는 강의실은 없다.

새로운 강의실을 찾아가도록..

-> 강의실 예약현황 = [5시, 6시 , 7시 , 6시]

 

이런 식으로 강의실 시간들을 갱신해주면 된다.

 

2-3) 시간복잡도 고려

 

여기까지 잘 구현했는데 시간초과가 계속 떴다.

 

결국 시간초과를 줄일 방법이 필요했고,

정렬의 시간복잡도를 O(nlogn)까지 줄여주는 heapq를 쓰기로 했다.

 

여기서 오름차순으로 정렬해야 하는 것은 두가지 상황이다.

1) 강의 시작시간이 빠른 강의부터 고려함 => 오름차순 정렬

2) 강의실 추가여부를 강의실 예약현황 중 가장 빨리 끝나는 시간과 비교 => 오름차순 정렬

 

이 두 가지를 heapq로 구현해주었더니 통과할 수 있었다.

 

---

3. 코드

#1374 - 강의실(골5)

import heapq

n= int(input())

#고려해야할 강의들 리스트
classa=[]

#빨리 끝나는 것부터 정렬
for _ in range(n):
  num, start, end = map(int, input().split())
  heapq.heappush(classa, (start, end))

#강의실 예약현황
room=[0]

for i in range(n):
  k= heapq.heappop(classa)
  
  #가장 빨리 끝나는 강의와 비교
  
  #만약 시작시간이 더 느리다면 -> 기존 강의실 시간 갱신
  if room[0] <=k[0]:
    heapq.heappop(room)
    heapq.heappush(room,k[1])
  
  #만약 시작시간이 더 빠르다면 -> 새로운 강의실 추가
  else:
    heapq.heappush(room, k[1])
print(len(room))

---

4.배운 점

확실히 heapq의 시간복잡도가 굉장히 좋다는 것을 체감할 수 있었던 문제.

특히 힙을 두개 사용해야 통과할 수 있을 정도로 빡빡한 시간조건이었기에

오름차순, 내림차순 등 정렬이 필요한 요소들을 파악하고 heapq로 구현하는 연습을 해야겠다는 생각이 들었다.