BOJ #3 : [22234] 가희와 은행 (py)

마참·2023년 1월 17일

PS

목록 보기

3/11

문제

가희는 창구가 하나인 은행을 운영하고 있습니다. 가희의 은행이 영업을 시작했을 때, 대기 줄에는 손님이 N명 있습니다.

카운터 직원과 N명의 손님

x번 손님에 대한 정보는 x번 손님의 id 값인 Px와 업무를 처리하는 데 필요한 시간인 tx초로 정보가 주어지게 됩니다.

은행이 영업을 시작하고 난 후에 들어오는 손님은 M명 있습니다. 이 손님들은 입력을 받은 순서대로 각각 N+1, N+2, ..., N+M번 손님이 됩니다.

이 손님들에 대한 정보는 x번 손님의 id 값인 Px와 업무를 처리하는 데 필요한 시간인 tx초, 영업 시작 cx초 후에 들어왔다는 정보가 주어지게 됩니다.

손님은 은행에 들어옴과 동시에, 대기 큐의 맨 뒤에 서게 됩니다. N+1번 손님이 은행을 영업을 시작하고 cN+1초 후에 들어왔다고 생각해 보겠습니다.

은행이 영업을 시작하고 cN+1초 후 상황

N+1번 손님은 은행에 들어오자 마자 대기 큐의 맨 뒤에 줄을 서게 되므로, 영업을 시작하고 cN+1초 후에 대기 큐의 상태는 위와 같습니다.

창구에 있는 직원과 고객들은 아래와 같은 알고리즘으로 업무를 처리합니다.

대기 큐의 맨 앞에 있는 고객이 x번 손님이라고 하면, 창구에 있는 직원은
tx가 T보다 크다면, x번 손님의 업무를 T초동안 처리합니다. 그 후, x번 손님의 업무가 끝나는 데 필요한 시간인 tx는 T만큼 감소합니다.
그렇지 않으면, x번 손님의 업무를 tx초 동안 처리합니다. 이후에, x번 손님의 업무가 끝나는 데 필요한 시간인 tx는 은 0이 됩니다.
대기 큐의 맨 앞에 있는 고객인 x번 손님은
업무가 끝나는 데 필요한 시간인 tx가 0이 되었다면, 은행 바깥으로 나가게 됩니다.
그렇지 않으면 대기 큐의 맨 뒤로 이동하게 됩니다. 만약에 이 때 도착한 손님이 있다면, 도착한 손님 뒤로 가게 됩니다.
대기 큐에 고객이 남았다면 1로 돌아갑니다.
은행이 영업을 시작할 때 부터 창구에 있는 직원은 일을 시작합니다.

은행이 영업을 시작한 시점으로부터 0초가 지났을 때 부터 W-1초가 지날 때 까지 창구에 있는 직원이 어떤 고객의 업무를 처리하는지 알려주세요.

입력

첫 번째 줄에 N과 T, W가 공백을 구분으로 해서 주어집니다.

두 번째 줄 부터 N개의 줄에는 0초일 때, 대기 큐의 앞에 있는 고객부터, Px와 고객이 일을 처리하는 데 필요한 시간 tx가 공백으로 구분되어 주어집니다.

N+2번째 줄에는, 1초 이후에 은행에 들어온 고객 수 M이 주어집니다.

N+3번째 줄부터 M개의 줄에 걸쳐서, Px, tx, cx가 공백으로 구분되어 주어집니다. 입력된 순서대로 각각 N+1, ..., N+M번 고객입니다.

이는 고객 id가 Px인 고객은 일을 처리하는 데 필요한 시간이 tx초이고, 영업 시작 시간으로부터 cx초가 지났을 때 은행에 들어왔다는 것을 의미합니다.

출력

i번째 줄에는 은행이 영업을 시작한 시점으로부터 i-1초가 지났을 때 은행 직원이 처리하고 있는 고객 id를 출력해 주세요.

제한

N, T, W, M는 구간 [1, 2×10^5]에 속하는 정수입니다.
0초부터 W-1초까지 모든 순간에 대기 큐가 비어 있는 경우는 존재하지 않습니다.

고객이 일을 처리하는 데 걸리는 시간은 구간 [1, 10^9]에 속하는 정수입니다.

고객 id는 구간 [1, 10^9]에 속하는 정수이고, 중복되지 않습니다.

[N+1, N+M]에 속하는 임의의 정수 x에 대해, cx는 구간 [1, 10^9]에 속하는 정수이며, 중복되지 않습니다.

즉, 영업을 시작하고 난 후에는 같은 시간에 2명 이상이 동시에 들어오지 않습니다.
BOJ 22234

문제 설명

간단하게, 각 초마다 누구의 업무를 하고 있는지를 출력하는 문제이다.

먼저 초기 대기열이 주어지고 추가 고객이 언제 오는지가 주어진다.
각 고객의 데이터에는 id 와 업무를 처리하는데 걸리는 시간이 주어진다.

T값도 주어지는데 이는 한명당 처리할 수 있는 최대 시간이다. 이 시간을 초과하면 얄짤없이 줄을 다시서야한다.

코드

import sys
from collections import deque

input = sys.stdin.readline


def solve():
    N, T, W = map(int, input().split())

    # 대기열 = [id, 남은 시간]
    waiting = deque(list(map(int, input().split())) for _ in range(N))

    M = int(input())
    # 고객 = [id, 남은 시간, 영업 시작후 들어오는 시간]
    customer = [list(map(int, input().split())) for _ in range(M)]
    customer.sort(key=lambda x: -x[2])  # 시간에 따라 정렬한다.

    # 결과 = [id, 반복 회수]
    result = []

    elapsed = 0
    while elapsed < W:
        e = waiting.popleft()

        if e[1] < T:
            # 한번에 처리하는 경우
            elapsed += e[1]
            result.append([e[0], e[1]])
            e[1] = 0
        else:
            # 줄을 다시 서는 경우
            e[1] -= T
            result.append((e[0], T))
            elapsed += T

        # 대기열에 추가할 목록
        temp = []
        while customer and customer[-1][2] <= elapsed:
            temp.append(customer.pop())
            temp.sort(key=lambda x: -x[2])

        while temp:
            waiting.append(temp.pop())

        # 되돌아 가는 경우 가장 뒤로 선다.
        if e[1]:
            waiting.append(e)

    time = 0
    for idx in range(len(result) - 1):
        for _ in range(result[idx][1]):
            print(result[idx][0])
        time += result[idx][1]

    cnt = result[-1][1]
    while cnt and time < W:
        time += 1
        cnt -= 1
        print(result[-1][0])


if __name__ == "__main__":
    solve()