문제

1. 회전판에 N개의 음식이 있고, 각 음식을 섭취하는데 일정 시간이 소요된다.
2. 무지는 1번 음식부터 먹기 시작하여, 순서대로 1초씩 섭취하고 다음 음식을 섭취한다.
3. 다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식이다.
4. N번까지 먹었으면 다시 1번으로 돌아온다.
5. K초 후에 먹어야 할 음식은 무엇인지 찾는 프로그램을 만든다.

아이디어

핵심 아이디어

카카오 코딩 테스트 - 무지의 먹방 라이브 (Java 풀이) - ezsw님의 유튜브 풀이 영상

정확성만 통과하는 아이디어

1. k번 움직이며 모든 음식을 체크한다.
2. 만약 현재 먹는 음식을 이미 다 먹었다면, 다음 먹을 수 있는 음식을 찾아 먹는다.

정확성, 효율성 모두 통과하는 아이디어.

• 1칸씩 k번 이동하여 k번까지 도착하는 것을, N칸씩 움직여 k까지 이동하는것으로 이동횟수를 줄인다.
• 다 먹은 음식을 효율적으로 skip한다.

이 두가지를 구현하기 위해 food_time = [3, 2, 3, 4, 7, 7], k = 19을 예시로 할 때,
1. 음식 섭취시간food_time을 오름차순으로 정렬한다.

2. 적은 시간이 드는 음식을 모두 먹는 시간만큼, 모든 음식들을 먹는다.
이 과정을 통해 1칸씩 k번 이동이 아닌 N칸씩 이동하여 k번 이동을 한다.
모든 음식에 음식 2를 먹기위한 시간 2를 사용한다. 이를 통해 한번에 2 * 6 = 12의 시간을 점프할 수 있다.
이 때, 남은 시간 k = k - 12 = 7이 된다.

3. 위의 과정후, 음식 1을 먹기위한 시간은 1이 남아있다. 이 시간을 남아있는 모든 음식에 사용한다. 이때 시간은 (원래 시간 - 이전에 사용한 시간) * 남아있는 음식의 수 = (3 - 2) * 5 = 4 이다.
이 때, 남은 시간 k = k - 5 = 2가 된다.
이 때, 음식 2는 자연스럽게 skip하여 다 먹은 음식을 효율적으로 스킵할 수 있다.

4. 음식 3은 3의 과정 (먹는 시간이 같은 다른 음식 계산과정중)에 모두 먹은것을 확인할 수 있으므로 넘어갈 수 있다.
5. 음식 4를 모두 먹기 위한 시간은 1이 남아있다. 이 시간을 남아있는 모든 음식에 사용하기 위해서는 1 * 3 = 3의 시간이 필요하다. 하지만 이 때 남은 시간 k = 2이므로 모든 음식을 먹을 수 없다.
6. 즉 k < 음식을 먹기 위한 시간이 되는 시점 부터는 음식을 하나하나 먹어가며 시간을 체크해야 한다.
7. 위의 예시의 경우에는 4,5,6의 음식이 남아있고, 4번 음식부터 순서대로 먹어가며 남ㅇ은 k시간을 채워나간다.
8. k시간동안 5번음식까지 먹을 수 있으므로 답은 6번을 먹을 차례이다.

구현 아이디어

1. food_times의 정렬은 heapq로 만들어서 구현한다. 이 때, heapq의 각 인덱스의 값은 [times, idx]가 된다.
2. while반복문으로 heapq의 길이가 0이 될때까지 반복한다.
3. heapq의 맨 앞값을 보면서 해당 음식을 모두 먹는시간 * 남은 음식갯수를 계산한다.
4. 만약 k >= 해당 음식을 모두 먹는시간 * 남은 음식갯수라면 다음으로 시간이 적게 걸리는 음식을 먹는다. 이 때, heappop()과 남은 음식갯수를 -1 한다.
5. 만약 k < 해당 음식을 모두 먹는시간 * 남은 음식갯수 이 된다면, 남은 heapq를 idx기준 오름차순 정렬 후 k % 남은 음식 갯수인 인덱스의 값을 반환한다.

코드

import heapq
def solution(food_times, k):
    answer = -1
    leftover = len(food_times)  # 남은 음식의 갯수.
    food_heap = [[time, idx + 1] for idx, time in enumerate(food_times)]
    heapq.heapify(food_heap)
    prev_time = 0
    while food_heap:
        food_time, food = food_heap[0]  # 전부 먹는 시간, 먹을 음식
        eat_time = (food_time - prev_time) * leftover  # 현재 음식의 남은 갯수만큼 모든 음식을 먹을때 걸리는 시간.
        if k >= eat_time:
            k -= eat_time
            prev_time = heapq.heappop(food_heap)[0]
            leftover -= 1
        else:
            food_heap.sort(key=lambda x: x[1])  # 인덱스 순으로 다시 정렬
            return food_heap[k % leftover][1]
    return answer

정확성만 통과하는 코드

실제로 시험본다면 효율성 통과하는 코드를 작성하지 못하는 경우가 많다.
카카오 문제같은 경우 효율성 문제가 있을 때, 정확성 코드의 경우 생각보다 간단하게 풀이되는 경우가 있는데
이 문제 또한 정답률: 정확성 42.08% / 효율성 5.52%으로 많은 사람이 효율성을 통과하지 못했지만 정확성은 많은 사람이 통과했다.
만약 효율성 테스트가 있는 문제의 경우 효율성을 못풀겠다고 문제를 바로 포기하는것보다는 간단한 코드로라도 정확성은 통과시켜두는것이 좋다고 생각한다.
22카카오 채용때 정확성만 급하게 풀어서 낸 덕분에 합격해보았기 때문이다.

def next_idx(food_times, k):
    while True:
        k = (k + 1) % len(food_times)
        if food_times[k] != 0:
            return k


def simple_solution(food_times, k):
    idx, cnt = 0, 0
    MAX = sum(food_times)
    while True:
        # print(idx, cnt)
        if cnt == MAX - 1:
            return -1
        if cnt == k - 1:
            return next_idx(food_times, idx) + 1
        if food_times[idx] != 0:
            food_times[idx] -= 1
            cnt += 1
        idx = next_idx(food_times, idx)
    return answer