[백준] 싸지방에 간 준하

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

12764번: 싸지방에 간 준하

우선순위 큐와 dict 자료구조를 활용하여 풀이했습니다. 먼저, 컴퓨터의 최소 개수를 알아야합니다. time이라는 dict에 각 군인이 사용 시작에는 1을 사용 종료에는 -1을 넣어주고 시간을 오름차순으로 탐색하면서 누적합이 최대가 될때가 기다리지 않고 컴퓨터를 쓸 수 있는 최소의 개수가 됩니다. 

 

최소 컴퓨터의 개수를 알았으니 다음으로는 각 컴퓨터가 얼마나 사용되었는지를 알아야합니다. 아까와 같은 방식으로 time dict에 사용시작과 종료를 넣어주는데 이번에는 어떤 사용자가 사용시작, 종료를 했는지 알기 위해 각각의 인덱스를 활용하여 넣어줍니다. 만약, 어떤 군인이 컴퓨터를 사용시작하려고 하면 컴퓨터 번호가 담겨있는 우선순위 큐에서 하나를 뽑아서 사용해주도록하고 현재 인덱스의 군인이 어떤 컴퓨터를 사용했는지를 기록해줍니다. 사용 종료시에는 군인이 사용했던 컴퓨터 번호를 다시 우선순위 큐에 넣어주면 됩니다.

 

import sys, heapq
from collections import defaultdict
#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n = int(input())

time = defaultdict(int)

hours_of_use = []
# 각 군인들의 사용시간의 시작과 끝을 넣어준다.
for _ in range(n):
    start, end = tuple(map(int, input().split()))
    hours_of_use.append((start, end))

    time[start] += 1
    time[end] -= 1

maxCom = 0
cur = 0
for t in sorted(time.keys()):
    cur += time[t]
    maxCom = max(cur, maxCom)
# 각 컴퓨터가 사용된 횟수
used = [0 for _ in range(maxCom + 1)]
# 현재 가장 작은 번호의 사용되지 않는 컴퓨터 번호를 알려줄 pq
pq = [x for x in range(1, maxCom + 1)]
# 각 군인이 사용한 컴퓨터 번호
sol = [0 for x in range(n + 1)]

time = defaultdict(int)
# 각 사용자의 시작시간과 끝나는 시간을 넣어준다
for i, use in enumerate(hours_of_use):
    time[use[0]] = i + 1
    time[use[1]] = -(i + 1)

for t in sorted(time.keys()):
    # 이용을 시작하는 경우
    # 사용되지 않는 가장 작은 컴퓨터 번호를 pq에서 뽑아서 사용하도록 한다.
    if time[t] > 0:
        cur_com = heapq.heappop(pq)
        sol[time[t]] = cur_com
        used[cur_com] += 1
    # 이용이 끝나는 경우
    else:
        using_com = sol[-1 * time[t]]
        heapq.heappush(pq, using_com)

print(maxCom)
print(*used[1:])