[파이썬/python] 백준 - 12764 싸지방에 간 준하

문제

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

---

문제 설명

1. N명의 사람이 주어진다.
2. 각 사용자의 컴퓨터 이용 시작 시각 P와 종료 시각 Q가 주어진다. 
3. 컴퓨터 자리는 1번부터 순서대로 번호가 매겨져 있으며, 비어있는 자리 중 번호가 가장 작은 자리에 앉아야 한다.
4. 모든 사람이 기다리지 않고 이용할 수 있는 컴퓨터의 최소 개수와 몇 명의 사람이 사용했는가를 구한다.

 

---

풀이

1. 아직 싸지방에 들어가지 않은 사람들을 hq에 저장한다.
   1. 이용시간이 가장 빠른 사람 먼저 힙에서 꺼낸다.
2. 다음에 이용할 사람을 hq에서 꺼낸 후 어느 자리에 들어갈 수 있는지 검증한다.
   1. 이용중인 사람을 저장한 hq2에서 종료시간이 가장 빠른 사람을 꺼낸다.
   2. 다음 사람이 들어왔을 시점에 이미 사용이 종료한 사람이라면 hq2에서 전부 꺼내고 해당 자리를 비운다.
3. 비운 자리 중 가장 낮은 번호의 자리에 다음 사람을 넣는다.
   1. 이 때 만약 자리가 없다면, 새로운 컴퓨터를 생성한다.

---

코드

import sys
import heapq
input = sys.stdin.readline

N = int(input())
hq = [list(map(int,input().split())) for _ in range(N)]

heapq.heapify(hq)

com = []
hq2 = []
dic = {0:0}
max_i = 0
while hq:
    nst,net = heapq.heappop(hq)
    while hq2:
        et,st,i = heapq.heappop(hq2)
        if et <= nst:# 사용 종료
            heapq.heappush(com,i)
            continue
        else:
            heapq.heappush(hq2,(et,st,i))
            break
    if not com:
        dic[max_i] = 1
        ni = max_i
        max_i += 1
    else:
        ni = heapq.heappop(com)
        dic[ni] += 1
        
    heapq.heappush(hq2,(net,nst,ni))
print(len(dic))
print(*dic.values())

---

시간복잡도

• hq에서 N개의 원소를 전부 꺼내기 때문에 $NlogN$, 다음 사람이 들어올 때 사용자를 hq2에서 빼낼 때 결과적으로는 총 N개의 사람을 빼낼 수 있기 때문에, 총합 $NlogN + N$으로 예상할 수 있다.
• 시간복잡도는 약 $O(NlogN) = O(10^5 *20) = O(10^6)$ 정도 소요된다.