[Python] [BOJ] 싸지방에 간 준하(12764)

💡 문제 해결

1. 먼저 온 사람이 컴퓨터를 사용하기 때문에 시작시간에 따라 정렬
2. 만일 컴퓨터를 사용중인 사람이 없거나 가장 빨리 종료하는 사람의 시간이 시작시간보다 뒤일 경우 자리 사용개수 증가
3. 하지만 빈 자리가 있을 경우 빈 자리에 배치
4. 가장 빨리 종료하는 사람의 시간이 시작시간보다 빠를 경우 해당 자리에 배치하고 empty_seat 빈 자리 리스트에 자리 번호를 추가
5. 자리 사용 횟수를 나타내는 use_seat_num을 출력

🧾 문제 설명

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

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

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

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

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

문제보기

🖨 입출력

📝 풀이

import sys, heapq

input = sys.stdin.readline

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

people.sort()

heap = []
cnt = 0
empty_seat = []
use_seat_num = [0] * (N + 1)
using = [False] * (N + 1)
for start, end in people:
    if (not heap or heap[0][0] > start):
        if empty_seat:
            seat_num = heapq.heappop(empty_seat)
            use_seat_num[seat_num] += 1
            heapq.heappush(heap, (end, seat_num))
        else:
            cnt += 1
            use_seat_num[cnt] += 1
            using[cnt] = True
            heapq.heappush(heap, (end, cnt))
    else:
        while heap[0][0] < start:
            seat_num = heapq.heappop(heap)[1]
            heapq.heappush(empty_seat, seat_num)
            if len(heap) == 0: break
        min_seat_num = heapq.heappop(empty_seat)
        use_seat_num[min_seat_num] += 1
        heapq.heappush(heap, (end, min_seat_num))

answer = using.count(True)
print(answer)

for use_seat in use_seat_num[1:]:
    if use_seat:
        print(use_seat, end=' ')
    else: break

• 출처: BAEKJOON Online Judge
• 링크: https://www.acmicpc.net/problem/12764