이 포스팅에서는 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 카카오 블라인드 채용 무지의 먹방 라이브
합격왕 우여곡절 끝에 드디어 합격왕에 광고를 붙였다. 서비스를 시작한지 무려 4년이 지나서야 드디어 광고를 시작하게…
반복적인 일상 매일 아침 일어나 회사에 출근하고, 저녁을 먹고 돌아오는 일상의 반복이다. 주말은 가족을 보러…
Planning A well-structured plan has the following characteristics: First, the ultimate vision you aim to…
English The most common problem for English learners like myself is that we often use…
This website uses cookies.