[카카오] 2019 KAKAO BLIND RECRUITMENT 1차 풀이 – 무지의 먹방 라이브

이 포스팅에서는 2019 카카오 블라인드 채용 1차 문제인 ‘무지의 먹방 라이브’ 문제를 해설합니다. 본 풀이에 대한 테스트는 https://programmers.co.kr/learn/courses/30/lessons/42891에서 수행하였으며 공식 풀이와 일치하지 않을 수 있습니다.

공식 풀이는 링크를 참조하시기 바랍니다.


무지의 먹방 라이브

출처 : 2019 KAKAO 블라인드 채용 온라인 1차
링크 : https://programmers.co.kr/learn/courses/30/lessons/42891
카테고리 : Greedy, Sorting
난이도 : 쉬움


문제 설명

리스트에 Integer 값으로 음식의 양이 주어진다. 무지는 음식을 가장 첫 번재 인덱스부터 차례로 돌아가며, 매 초에 1씩 먹을 수 있다. 맨 끝의 음식을 먹은 후에는 다시 가장 왼쪽에 있는 접시의 음식부터 먹어야한다.

K초의 시점에 먹어야 할 음식이 무엇인지 출력하여라.


문제 풀이

각 접시에 대해 [음식의 양, 인덱스]를 저장한 후 음식의 양과 인덱스에 대해 오름차순으로 정렬한다.

가장 적은 양의 접시를 비우는 문제에 대해 생각해보자. 만약 가장 양이 적은 접시에 X만큼의 음식이 있고, 식탁에 N개의 접시가 있다면 이 접시를 비우고 다시 맨 왼쪽 접시로 돌아오기 위해서는 최소 X * N초가 걸린다.

만약 그보다 시간이 적게 남았다면 왼쪽부터 돌아가면서 음식을 먹었을 때, 어떤 접시도 바닥나지 않을 것이므로 K초 이후에 먹어야 할 음식은 K % N번째 접시에 있을 것이다.

만약 그보다 시간이 많이 남았다면 K초에서 X * N초를 제거하고, 해당 접시를 제거한 후에 다시 똑같은 과정을 반복하면 된다. 여기에서 N은 1 감소하고, 모든 접시에서 X만큼의 음식이 감소해야한다.

현재 시점에서 가장 적은 음식이 남아있는 접시의 음식 양이 얼마인지는 그 이전 시점에 최소 접시의 양과 현재 시점의 최소 접시 양을 빼면 쉽게 구할 수 있다.


정답 코드

def solution(food_times, k):
    # 각 접시의 음식량과 인덱스를 저장 후 음식량 기준 오름차순 정렬
    for i in range(len(food_times)):
        food_times[i] = [food_times[i], i]
    food_times.sort()
 
    # 아직 음식이 남아있는 접시의 인덱스를 저장
    remained = set([i for i in range(len(food_times))])
 
    prev = 0
    # 음식량이 적은 것부터 많은 것 순으로 탐색
    for i in range(len(food_times)):
        # 음식 먹는 방식은 한 바퀴를 쭉 도는 것이므로, 이전 접시를 다 비웠다면
        # 현재 접시에 남은 음식 양은 원래 양과 이전 접시의 차이만큼 남아있다
        delta = food_times[i][0 prev
        prev = food_times[i][0]
        # 현재 접시에 남은 음식을 다 비운다고 하면 그 양만큼
        # 다른 접시들의 음식도 먹어야한다. 모든 접시들에서 현재 접시의 양만큼을
        # 먹을 수 있을만큼 시간이 남았으면 현재 상태에서 마지막 인덱스를 구할 수
        # 없으므로 접시를 제거하고, 소요되는 시간을 빼준다.
        if k >= delta * len(remained):
            k = delta * len(remained)
            remained.remove(food_times[i][1])
        else:
            # 완전히 다 비우고도 한 바퀴를 다시 돌 수 없다면 마지막 위치를
            # 나머지 연산으로 구할 수 있다.
            answer = list(remained)[k % len(remained)]
            # 접시의 인덱스가 1부터 시작하므로 보정
            return answer + 1
    return 1
cs

Competition 카카오 블라인드 채용 무지의 먹방 라이브