이 포스팅에서는 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 카카오 블라인드 채용 무지의 먹방 라이브
출장 오랜만에 출장을 간다. 미국으로 가는 출장은 항상 힘들다. 비행시간은 10시간에서 12시간. 도착해서 시차 극복도…
건강검진 재작년 말인가 작년 1월이었나, 인생 최악의 건강검진 결과를 받고서 다짐했었다. 2025년 건강검진에서는 완벽한 검사결과를…
운동 계획 운동과 식단과 피부관리 동시에 하니 시너지가 엄청나다. 변화가 눈에 보일 정도로 빠르다보니, 성취감도…
This website uses cookies.
