[카카오] 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 카카오 블라인드 채용 무지의 먹방 라이브