[백준] 12764번 싸지방에 간 준하

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

12764번: 싸지방에 간 준하

문제

현재 대한민국 해군에 소속되어있는 준하는 문제를 풀기 위해 매일같이 사이버 지식 정보방 통칭 싸지방에 다닌다. 그러나 최근 문제가 생겼다. 싸지방에 사람이 몰려 컴퓨터 수가 모자라게 된 것이다. 이런 사태를 도저히 용납할 수 없었던 준하는 곧 전역하는 선임을 설득해 민원을 넣도록 하는 데 성공했다.

마침내 부대에서는 민원을 받아들이기로 하였고, 컴퓨터를 증설하기로 했다. 또한, 컴퓨터 간의 사용률에 따라 다른 성능의 컴퓨터를 설치하고자 한다.

하지만 예산이 부족해 사람 수 만큼 컴퓨터를 살 수가 없었다. 고심에 고심을 거듭한 준하는 모든 사람이 항상 정해진 시간에 싸지방을 이용한다는 사실을 발견했다.

컴퓨터가 있는 자리에는 1번부터 순서대로 번호가 매겨져 있다. 모든 사람은 싸지방에 들어왔을 때 비어있는 자리 중에서 번호가 가장 작은 자리에 앉는 것이 규칙이다.

준하가 발견한 사실과 이용 규칙을 가지고, 모든 사람이 기다리지 않고 싸지방을 이용할 수 있는 컴퓨터의 최소 개수와 자리별로 몇 명의 사람이 사용했는가를 구하시오.

 

입력

첫째 줄에 사람의 수를 나타내는 N이 주어진다. (1≤N≤100,000) 둘째 줄부터 N개의 줄에 걸쳐서 각 사람의 컴퓨터 이용 시작 시각 P와 종료 시각 Q가 주어진다. (0≤P<Q≤1,000,000)

시작 시각이나 종료 시각이 다른 사람과 겹치는 경우는 없다.

 

출력

첫째 줄에 사람이 모든 사람이 기다리지 않아도 되는 컴퓨터의 최소 개수 X를 출력한다.

둘째 줄에는 1번 자리부터 X번 자리까지 순서대로 각 자리를 사용한 사람의 수를 띄어쓰기 간격으로 출력한다.

 

 

풀이

N이 10만이기 때문에 단순탐색으로 자리를 찾는 경우에는 시간 조건을 통과시킬 수 없다.

 

time_set = [list(map(int, sys.stdin.readline().split()))for _ in range(N)]
time_set.sort(key=lambda x: (x[START], x[END]))
time_set = deque(time_set)

먼저 입력 받은 시작과 끝나는 시간을 정렬하고 앞에서부터 가져올 수 있게 하기위해 deque를 사용했다.

 

empty = [i for i in range(N)]
heapq.heapify(empty)            #사용할 수 있는 컴퓨터

사용하는 컴퓨터의 최대 수는 사람 수이기 때문에 사람 수만큼의 번호를 넣어서 비어있는 컴퓨터를
나타내는 heap을 구성하였다. 항상 가장 낮은 번호의 비어있는 컴퓨터가 맨 위에 위치한다.

 

while time_set:
    tick += 1
    if tick == time_set[0][START]:
    	# temp의 START는 시작시간 END는 종료시간
        temp = time_set.popleft()
        idx = heapq.heappop(empty)
        # 종료시간인 temp[END] 기준으로 min heap을 구성하기 위해 반대로 입력
        heapq.heappush(computers, [temp[END], temp[START], idx])
        count[idx] += 1

이제 time_set이 빌때까지 tick을 1씩 증가시키면서 time_set의 0번에 있는 시작 시간이 tick과 동일한 경우에
꺼낸 뒤 heap에 넣었다. heap에는 종료 시간이 먼저들어가게 하여 종료 시간을 기준으로 min heap을 생성하여
가장 빨리 종료하는 사람이 heap에 맨 위에 오게 설정하였다.

time_set의 0번을 확인하는 이유는 정렬된 time_set에서 앞에서부터 데이터를 pop하기 때문에 남아 있는 사람 중
가장 먼저 컴퓨터를 사용하는 사람이 항상 0번에 있다.

 

idx = heapq.heappop(empty)
count[idx] += 1

idx는 어떤 자리에 앉았는지 체크하기 위한 변수로 empty를 pop하면 가장 낮은 번호의 비어있는 컴퓨터가 나오기 때문에 가장 앞에 있는 컴퓨터에 앉을 수 있다.
count는 컴퓨터 idx에 앉은 횟수를 저장한다.

 

    if computers and computers[0][0] == tick:
        s, e, i = heapq.heappop(computers)
        heapq.heappush(empty, i)

heap에 가장 위에 있는 값이 현재 tick과 동일한 경우에는 pop하고 몇 번자리에 앉았는지 체크해서
empty heap에 다시 넣어 그 자리를 사용할 수 있게 변경하였다.

 

answer = [0]            # 0번은 갯수 1번부터 사용한 횟수
for i in count:
    if i == 0:
        break
    else:
        answer.append(i)
        answer[0] += 1
        

print(answer[0])
print(*answer[1:])

answer에 0번에는 총 필요한 컴퓨터의 수 1번부터는 사용횟수가 0이 아닌 컴퓨터를 순서대로 append했다.
예제에 대한 answer = [4, 1, 2, 1, 1]

 

 

 

전체 코드

import sys
import heapq
from collections import deque

START, END = 0, 1
N = int(sys.stdin.readline().strip())
time_set = [list(map(int, sys.stdin.readline().split()))for _ in range(N)]
time_set.sort(key=lambda x: (x[START], x[END]))
time_set = deque(time_set)
computers = []      #heap
empty = [i for i in range(N)]
heapq.heapify(empty)            #사용할 수 있는 컴퓨터
tick = -1
count = [0 for _ in range(N)]
answer = [0]            # 0번은 갯수 1번부터 사용한 횟수

while time_set:
    tick += 1
    if tick == time_set[0][START]:
        temp = time_set.popleft()
        idx = heapq.heappop(empty)
        heapq.heappush(computers, [temp[END], temp[START], idx])
        count[idx] += 1
    if computers and computers[0][0] == tick:
        s, e, i = heapq.heappop(computers)
        heapq.heappush(empty, i)

for i in count:
    if i == 0:
        break
    else:
        answer.append(i)
        answer[0] += 1

print(answer[0])
print(*answer[1:])

변수가 많아서 조금 복잡하지만 중요한건 heap을 이용하여 비어있는 컴퓨터와 종료하는 사람을 찾아
O(N^2)으로 풀지 않는 것이 핵심인것 같다.