Baekjoon 22234
in Study / Computer science on Baekjoon 22234
Queue
Description
가희는 창구가 하나인 은행을 운영하고 있습니다. 가희의 은행이 영업을 시작했을 때, 대기 줄에는 손님이 N명 있습니다.
x번 손님에 대한 정보는 x번 손님의 id 값인 Px와 업무를 처리하는 데 필요한 시간인 tx초로 정보가 주어지게 됩니다.
은행이 영업을 시작하고 난 후에 들어오는 손님은 M명 있습니다. 이 손님들은 입력을 받은 순서대로 각각 N+1, N+2, …, N+M번 손님이 됩니다.
이 손님들에 대한 정보는 x번 손님의 id 값인 Px와 업무를 처리하는 데 필요한 시간인 tx초, 영업 시작 cx초 후에 들어왔다는 정보가 주어지게 됩니다.
손님은 은행에 들어옴과 동시에, 대기 큐의 맨 뒤에 서게 됩니다. N+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초가 지날 때 까지 창구에 있는 직원이 어떤 고객의 업무를 처리하는지 알려주세요.
Input
첫 번째 줄에 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초가 지났을 때 은행에 들어왔다는 것을 의미합니다.
Output
i번째 줄에는 은행이 영업을 시작한 시점으로부터 i-1초가 지났을 때 은행 직원이 처리하고 있는 고객 id를 출력해 주세요.
Condition
N, T, W, M는 구간 [1, 2×105]에 속하는 정수입니다.
0초부터 W-1초까지 모든 순간에 대기 큐가 비어 있는 경우는 존재하지 않습니다.
고객이 일을 처리하는 데 걸리는 시간은 구간 [1, 109]에 속하는 정수입니다.
고객 id는 구간 [1, 109]에 속하는 정수이고, 중복되지 않습니다.
[N+1, N+M]에 속하는 임의의 정수 x에 대해, cx는 구간 [1, 109]에 속하는 정수이며, 중복되지 않습니다. 즉, 영업을 시작하고 난 후에는 같은 시간에 2명 이상이 동시에 들어오지 않습니다.
Example I & O
Input 1
1 5 7
1 6
1
3 1 5
Output 1
1
1
1
1
1
3
1
Input 2
1 3 10
1 6
2
3 4 5
2 4 2
Output 2
1
1
1
2
2
2
1
1
1
3
My solution
from collections import deque
import sys
def heapSort(a1, a2, a3):
for i in range(len(a3)):
c = i
while c != 0:
r = (c - 1)//2
if a3[r] < a3[c]:
a1[r], a1[c] = a1[c], a1[r]
a2[r], a2[c] = a2[c], a2[r]
a3[r], a3[c] = a3[c], a3[r]
c = r
for j in range(len(a3) - 1, -1, -1):
a1[0], a1[j] = a1[j], a1[0]
a2[0], a2[j] = a2[j], a2[0]
a3[0], a3[j] = a3[j], a3[0]
r = 0
c = 1
while c < j:
c = 2 * r + 1
if c < j - 1 and a3[c] < a3[c + 1]:
c += 1
if c < j and a3[r] < a3[c]:
a1[r], a1[c] = a1[c], a1[r]
a2[r], a2[c] = a2[c], a2[r]
a3[r], a3[c] = a3[c], a3[r]
r = c
input = sys.stdin.readline
N, T, W = map(int, input().split())
ids = [0]
times = [0]
cs = [0]
for i in range(1, N + 1):
ID, Time = map(int, input().split())
ids.append(ID)
times.append(Time)
cs.append(0)
M = int(input())
extraID = []
extraTime = []
extraCs = []
for i in range(N + 1, N + M + 1):
ID, Time, Cs = map(int, input().split())
extraID.append(ID)
extraTime.append(Time)
extraCs.append(Cs)
heapSort(extraID, extraTime, extraCs)
ids.extend(extraID)
times.extend(extraTime)
cs.extend(extraCs)
currentTime = 0
waitList = deque([i for i in range(1, N + 1)])
minIndexForCx = N + 1
flag = True
while (flag):
processingNumber = waitList.popleft()
processingId = ids[processingNumber]
processingTime = times[processingNumber]
if processingTime > T:
for i in range(T):
sys.stdout.write(str(processingId) + "\n")
currentTime += 1
if currentTime == W:
flag = False
break
if minIndexForCx <= N + M and currentTime == cs[minIndexForCx]:
waitList.append(minIndexForCx)
minIndexForCx += 1
times[processingNumber] -= T
waitList.append(processingNumber)
else:
for i in range(processingTime):
sys.stdout.write(str(processingId) + "\n")
currentTime += 1
if currentTime == W:
flag = False
break
if minIndexForCx <= N + M and currentTime == cs[minIndexForCx]:
waitList.append(minIndexForCx)
minIndexForCx += 1
times[processingNumber] = 0
- Code Analysis
def heapSort(a1, a2, a3):
for i in range(len(a3)):
c = i
while c != 0:
r = (c - 1)//2
if a3[r] < a3[c]:
a1[r], a1[c] = a1[c], a1[r]
a2[r], a2[c] = a2[c], a2[r]
a3[r], a3[c] = a3[c], a3[r]
c = r
for j in range(len(a3) - 1, -1, -1):
a1[0], a1[j] = a1[j], a1[0]
a2[0], a2[j] = a2[j], a2[0]
a3[0], a3[j] = a3[j], a3[0]
r = 0
c = 1
while c < j:
c = 2 * r + 1
if c < j - 1 and a3[c] < a3[c + 1]:
c += 1
if c < j and a3[r] < a3[c]:
a1[r], a1[c] = a1[c], a1[r]
a2[r], a2[c] = a2[c], a2[r]
a3[r], a3[c] = a3[c], a3[r]
r = c
A function for heap sort
Sorting a3 as ascending order
Elements of a1 & a2 are relocated as the result of sorting a3
N, T, W = map(int, input().split())
ids = [0]
times = [0]
cs = [0]
for i in range(1, N + 1):
ID, Time = map(int, input().split())
ids.append(ID)
times.append(Time)
cs.append(0)
0 second : N customers
no need to sort N customers as problem’s condition
cs : list of cx (N customers have no cx value)
M = int(input())
extraID = []
extraTime = []
extraCs = []
for i in range(N + 1, N + M + 1):
ID, Time, Cs = map(int, input().split())
extraID.append(ID)
extraTime.append(Time)
extraCs.append(Cs)
heapSort(extraID, extraTime, extraCs)
ids.extend(extraID)
times.extend(extraTime)
cs.extend(extraCs)
After 0 second
should use sort function for sorting based on ascending order of Cx
currentTime = 0
waitList = deque([i for i in range(1, N + 1)])
minIndexForCx = N + 1
flag = True
currentTime : time check
waitList initialization : 1 ~ N (index) customer (0 second) minIndexForCx : index of current minimum Cx
while (flag):
processingNumber = waitList.popleft()
processingId = ids[processingNumber]
processingTime = times[processingNumber]
processingNumber : current customer (index) that is processed
processingId : current customer’s id processingTime : current customer’s time for processing
if processingTime > T:
for i in range(T):
sys.stdout.write(str(processingId) + "\n")
currentTime += 1
if currentTime == W:
flag = False
break
if minIndexForCx <= N + M and currentTime == cs[minIndexForCx]:
waitList.append(minIndexForCx)
minIndexForCx += 1
times[processingNumber] -= T
waitList.append(processingNumber)
In the case of (processingTime > T)
pass T seconds with processing current customer
If currentTime == W during processing, stop the program
If currentTime == cx of customer, the customer is added to waitList before uncompleted current customer is added to it
Current customer is added again to waitList with time - T
else:
for i in range(processingTime):
sys.stdout.write(str(processingId) + "\n")
currentTime += 1
if currentTime == W:
flag = False
break
if minIndexForCx <= N + M and currentTime == cs[minIndexForCx]:
waitList.append(minIndexForCx)
minIndexForCx += 1
times[processingNumber] = 0
In the case of (processingTime <= T)
pass processingTime seconds with processing current customer
If currentTime == W during processing, stop the program
If currentTime == cx of customer, the customer is added to waitList