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

문제

프로그래머스 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분 후에 심사대 앞에 도착한다.

1) k = 1인 경우
첫 번째 사람은 기다리지 않고 심사를 받는다. 두 번째 사람은 첫 번째 사람이 심사를 받은 직후, 심사를 받으므로 2분을 기다린다. 세 번째, 네 번째, 다섯 번째 사람은 각각 8분, 12분, 16분 기다린다. 따라서 5명이 심사대 앞에서 기다리는 평균시간은 (2+8+12+16)/5 =38/5 = 7.6분이다.

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

입력 형식

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

입력 예 - 1번

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

출력 예 - 1번

7.6

나의 코드

def sum_generator(arr, a, b): # arr[a]에서 arr[b]까지의 값을 구하는 방법
    arr = [0] + arr
    partial_sum = [0] * len(arr)

    for i in range(1, len(arr)):
        partial_sum[i] = partial_sum[i-1] + arr[i]
    partial_sum = partial_sum[1:]
    if a != 0:
        return partial_sum[b] - partial_sum[a-1]
    else:
        return partial_sum[b]

n = int(input())

waitt = 0 # 대기 시간
arvt = [] # 각 심사자의 도착 시간
judgt = [] # 각 심사자의 심사 시간
for y in range(n):
    arvt_idx, judgt_idx = map(int, input().split())
    arvt.insert(y, arvt_idx)
    judgt.insert(y, judgt_idx)

for i in range(0, n): # n까지 돌면서
    if i == 0: # i가 0일 때는 waitt는 0이다.
        continue
    elif i == 1:  # i가 1일 때
        if arvt[i] < judgt[i-1]: # 두번째 입국 심사자의 도착 시간이 첫번째 입국 심사자의 심사 시간보다 이른 경우
            waitt += judgt[i-1] - arvt[i]    # 심사시간에서 도착시간을 뺀 시간 이후에 심사를 받을 수 있으므로 이를 대기 시간에 더해준다.
        else:
            continue    # 두번째 입국 심사자의 도착 시간이 첫번째 입국 심사자의 심사 시간 이후인 경우. 이 떄는 입국 심사대가 비어있으므로 대기 시간이 없다.
    elif i >= 2: # i가 2 이상일 때
        waitt += sum_generator(judgt, 0, i-1) - sum_generator(arvt, 1, i) # (0번째부터 i-1번째 사람까지의 총 심사 시간) - (첫번째부터 i번째 사람까지의 총 대기 시간)

print(round(waitt/n, 1)) // 전체 대기 시간을 전체 인원으로 나눠준 후 소수점 둘째자리에서 반올림한다.

테스트 케이스 15개 중에 5개는 fail이지만, 어쨌든.. 한발짝 다가섰다. 이는 모든 사람이 전부 대기 시간이 있다는 전제 하에서는 다 들어 맞지만, 예를 들어

8
0 2
10 8
7 6
1 5
8 8
4 9
7 3
2 3

당장 이런 경우만 돼도 제대로된 결과가 나오지 않는다. 좀 더 고민해봐야겠다.