문제

무지의 먹방 라이브

접근

딱히 필요한 알고리즘은 없다.
당연하게도 k가 굉장히 크므로 k를 1씩 줄여가며 검사하면 효율성 테스트를 통과 못할 것이다.
k를 빠르게 줄여나갈 방법이 필요하다.

우선 k가 주어지는 배열 원소의 합보다 크거나 같으면 k초 후에 먹을 음식이 없다는 의미이므로 -1을 리턴한다.

이제 본격적으로 k를 어떻게 빠르게 줄여나갈지 생각해보자.
전체 배열의 원소를 한 바퀴돌고 오는데는 배열의 길이인 n번이 필요하다.
k가 n보다 크다면 충분히 한바퀴를 돌 수 있다는 의미이다.
여기서부터 접근을 하면 될 것 같다.
k가 n보다 크면 한바퀴를 돌리고, n보다 작으면 그 때부터 하나씩 줄여도 된다.
자 그러면 n보다 큰 경우에는 꼭 한바퀴씩만 돌려야할까?
배열을 정렬하자. 인덱스를 기억해야하므로, (val, idx)로 구성하고 val로 정렬했다면, val의 최소값을 통해서 몇 바퀴 회전할지 감을 잡을 수 있다.

우선 k 값에 상관하지말고, val의 최소값이 3이라고 하자.
그럼 3번 회전할 때까지는 비는 접시가 없을 것이다.
그럼 최대 3바퀴를 회전할 동안은 동일한 루트를 반복할 것이고, 변하는건 없을 것이다.

이제 k값에 따라 몇 번 회전할지를 정해야한다.
현재 배열의 최소값을 전부 회전해도 k가 남으면 전부 회전해도 된다.
아닌 경우는 k가 허용하는 한도내에서 회전을 해준다.

그리고 회전이 끝나면 회전한 횟수를 배열 원소들에서 빼줘야 한다.
예를 들어 5바퀴 회전을 했으면 배열 원소들에 모두 -5를 해줘야 한다.
근데 이 연산이 또 O(N)만큼 필요하겠지.
그래서 그냥 여태 회전한 횟수를 더해놓는 변수를 하나 두었다.
그럼 배열의 값에서 해당 변수를 빼면 남은 음식이 나올 것이다.
이 남은 음식이 0이면 배열에서 pop을 해준다.
deque으로 구성해서 pop(0)을 해줘도 되지만, 어짜피 한쪽에서만 빼줄테니 정렬을 반대로 해주고 맨 뒤에 최소값을 두는 식으로 구성했다.
그럼 이제 예를 들어 x바퀴를 돌았다고 했을 때, arr[-1]의 원소에서 x를 뺀 값이 0이면 pop해주는 것을 반복한다.
0보다 큰 값이 나오기전 까지.

이렇게 반복을 하다보면 어느 순간 남은 k가 배열의 길이 n보다 작아지는 순간이 온다.
참고로 n은 계속 변한다.
pop을 해줄 때마다 n을 줄여줘야겠지.

어쨋든 이제 더 이상 한바퀴를 돌 수 없다는 의미이다.
그럼 루프를 빠져나와서 인덱스를 기준으로 다시 정렬해준다.
그리고 남은 k는 결국 인덱스가 된다.
arr[k] 번째가 정답이 되는 것이다.
여기서 pop을 해주는 바람에 당연히 인덱스가 변했을 것이다.
앞에서 우리는 배열을 (val, idx)로 구성했으니 arr[k][1]이 k초 후에 먹을 음식의 원래 인덱스가 되는 것이다.
인덱스는 1부터 시작했으니 +1만 해주면 된다.

정리해보자.

k가 n보다 크거나 같으면 루프를 돈다.
k//n은 최대 몇 바퀴 돌 수 있는지를 의미한다.
예를 들어 k가 33이고 n이 10이면, 우리는 최대 3바퀴를 돌 수 있다. 이를 times라고 하자.
그리고 우리가 여태 몇 바퀴 돌았는지를 now라고 하자.
now는 처음엔 당연히 0이다.

그럼 이제 배열의 최소값에서 now를 뺀 값이 times보다 큰 경우가 있다.
즉, 최대로 회전했는데도 한 접시를 0으로 만들지 못했다는 의미이다.
이 경우는 배열에 변경사항이 없다.

변경해줄 부분은 now에 times를 더해준다.
times만큼 회전을 끝냈으므로.
그리고 k는 times*n을 빼준다.

반대의 경우, 즉, 접시를 0으로 만들 수 있는 경우에는 추가적으로 배열을 변경해줘야 한다.
자 위에서 구한 times는 최대 회전 수이다.
이제 최대 회전 수를 채울 수는 없으니까 times를 새로 구해야 한다.
배열의 최소값만큼 회전하면 되겠지.
최소값은 배열의 원소중 최소값에서 now를 뺀 걸 의미한다.
해당 값을 times로 두고 해당 값만큼 회전을 할 것이다.
배열의 최소값이 times랑 같으면 배열에서 pop해준다.
times랑 달라질 때까지 반복하면 된다.

코드

• 파이썬 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def preprocessing(food_times):
    food_times = [(item, idx) for idx, item in enumerate(food_times)]
    food_times = sorted(food_times, key = lambda x:(-x[0], x[1]))
    return food_times

def empty_food_pop(food_times, origin):
    times = food_times[-1][0] - origin
    while True:
        if food_times[-1][0] - origin == times:
            food_times.pop(-1)
        else:
            break
    return food_times, times

def solution(food_times, k):
    if k >= sum(food_times):
        return -1
    n = len(food_times)
    food_times = preprocessing(food_times)
    now = 0
    while k >= n:
        times = k // n
        if food_times[-1][0] - now <= times:
            food_times, times = empty_food_pop(food_times, now)
        now += times
        k -= (times * n)
        n = len(food_times)
    food_times = sorted(food_times, key = lambda x:x[1])

    return food_times[k][1]+1