[백준 / BOJ][Python] 19640 - 화장실의 규칙

[백준 / BOJ][Python] 19640 - 화장실의 규칙

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

19640번: 화장실의 규칙

걸린 시간

12 : 58

문제 풀이

문제 그대로 구현하면 되는 시뮬레이션 문제. 단 우선순위 큐를 사용하여 가장 먼저 사라질 원소를 관리해야 한다. 줄의 선두에 있는 사람들을 우선순위 큐에 넣고 삭제, 삽입을 반복하며 문제의 조건을 만족하면 반복을 그만둔다. 구현이 어렵지는 않지만 실수에 주의.

코드

import sys, heapq
from collections import deque
input = sys.stdin.readline

n, m, k = map(int, input().split())
person = [deque([]) for _ in range(m)]
for i in range(n):
    a, b = map(int, input().split())
    person[i % m].append((-a, -b, i % m, 1 if i == k else 0))
cnt = 0
pq = []
for i in range(m):
    if person[i]:
        heapq.heappush(pq, person[i][0])
while True:
    x = heapq.heappop(pq)
    person[x[2]].popleft()
    if x[3]:
        break
    else:
        cnt += 1
        if person[x[2]]:
            heapq.heappush(pq, person[x[2]][0])
print(cnt)