[알고리즘] 입국심사에서 각 입국 심사자의 평균 대기 시간 구하기(심사대 2개)

문제

프로그래머스 level3 입국심사 문제를 변형한 문제이다.
공항에서 사람들의 입국을 심사하는 심사대가 k(k = 1 혹은 2)개있다. 사람들이 입국심사를 받기 위하여, 심사대 바로 앞에서 한 줄로 서서 기다린다. k개의 심사대 중 하나가 비어있으면(심사받는 사람이 없으면), 먼저 도착한 사람이 비어 있는 이 심사대에서 심사를 받는다. 입국심사를 받기 위한 각 사람의 심사대 앞에 도착하는 시간과 심사받는데 걸리는 시간이 주어진다. 각 사람이 심사대 앞에 도착한 시간에 대한 정보는, 바로 이전 사람이 심사대 앞에 도착한 시간과의 차이(분)로 주어진다. 각 사람이 심사를 받기 위하여 기다리는 시간 (심사시간은 제외)의 평균을 소수점 이하 1자리까지 (소수점 이하 2째 자리에서 반올림) 출력하는 프로그램을 작성하시오.

5명의 사람들의 도착시간에 대한 정보가 0, 2, 1, 2, 1이고, 심사받는데 걸리는 시간이 각각 4분, 7분, 6분, 5분, 3분이라 하자. 5명의 도착시간에 대한 정보 0, 2, 1, 2, 1가 의미하는 것은 다음과 같다: 2번째 사람은 첫 번째 사람이 심사대 앞에 도착한 시간 2분 후에 심사대 앞에 도착하고, 3번째 사람은 2번째 사람이 도착한 시간 1분 후에 심사대 앞에 도착하고, 4번째 사람은 3번째 사람이 도착한 시간 2분 후에 심사대 앞에 도착하고, 5번째 사람은 4번째 사람이 도착한 시간 1분 후에 심사대 앞에 도착한다.

2) k = 2인 경우
심사대가 2개이므로 첫 번째 사람과 두 번째 사람은 각각 심사대 1과 심사대 2에서 기다리지 않고 심사를 받는다. 세 번째 사람은 1분을 기다리고 심사대 1에서 심사를 받는다. 네 번째 사람은 4분을 기다리고 심사대 2에서 심사를 받는다. 다섯 번째 사람은 4분을 기다리고 심사대 1에서 심사를 받는다. 따라서 5명이 심사대 앞에서 기다리는 평균시간은 (0 + 0 + 1 + 4 + 4) / 5 = 1.8분이다.

입력 형식

첫 번째 줄에 심사대 앞에 도착하는 사람들의 수 n이 주어진다. 다음의 각 줄에 먼저 온 사람부터 각 사람의 심사대 앞 도착시간에 대한 정보(분 단위 양의 정수)과 심사받는데 걸리는 시간(분 단위의 양의 정수)이 주어진다.

입력 예 - 2번

5 // n
0 4
2 7
1 6
2 5
1 3

출력 예 - 2번

1.8

나의 코드

arvt = []
judgt = []
k = int(input())

for i in range(k):
    arvt_idx, judgt_idx = map(int, input().split())
    arvt.insert(i, arvt_idx)
    judgt.insert(i, judgt_idx)

waitt = [0 for i in range(k + 1)]
pure_wait_time = [0 for i in range(k+1)]
sum_arvt = [0 for i in range(k + 1)]

num = 0
for i in range(len(arvt)):
    if arvt[i] != 0:
        num += arvt[i]
    sum_arvt[i] += num

k1 = sum_arvt[0] + judgt[0]
k2 = sum_arvt[1] + judgt[1]

for i in range(2, k):
    waitt[i] = sum_arvt[i] + min(abs(sum_arvt[i] - k1), abs(sum_arvt[i] - k2)) + judgt[i]
    pure_wait_time[i] = min(abs(sum_arvt[i] - k1), abs(sum_arvt[i] - k2))
    if k1 > k2:
        k2 = waitt[i]
    else:
        k1 = waitt[i]

print(round(sum(pure_wait_time)/k, 1))

풀이

K1(1번째 심사대), K2(2번째 심사대)에 처음 들어가는 사람은 대기시간이 0이므로, 각각 최초 도착 시간 + 심사시간 만 더해줬고, 3번째 사람부터 for문을 돌렸다.


i번째 사람이 총 걸린 시간(누적 도착시간 + 대기시간 + 심사시간)은, 누적 도착시간(sum_arvt[i])과 심사시간(judgt[i]), 그리고 대기시간(i번째 사람의 누적 도착시간과 K1, K2 시간의 차이 중 작은것) 으로 구성이 되어 있다. 이 문제는 대기시간을 나눈 값을 구해야 하므로, i번째 사람이 순수하게 대기한 시간(pure_wait_time[i])에 (i번째 사람의 누적 도착시간과 K1, K2 시간의 차이 중 작은것)을 더해줬다.


여기서, 최초 K1, K2의 값은 시간이 지나면서 당연히 바뀔 수밖에 없으므로, 최초 k1의 값이 더 클 경우 i번째 사람이 총 걸린 시간을 k2로 지정을 해 줬다. 왜냐면 이 경우에 i번째 사람은 k2(2번째 심사대)에 먼저 들어가게 되기 때문이다. 이렇게 k1이나 k2 값을 업데이트해준 후 다시 for문을 돌려서 각 상황에서의 순수 대기 시간을 구했다.

사실 이걸 .. 처음 과제로 나왔을 때는 완벽하게 풀지 못한 상태로 제출을 했었는데, 이번 과제(이 문제에서 심사대 2개를 k개로 일반화한 후 최소 힙을 이용해서 푸는 문제)를 풀고자 이 문제를 다시 만져보다가 얼떨결에 풀게 되었다.