이 포스팅에서는 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 카카오 블라인드 채용 무지의 먹방 라이브
AI AI Agent들이 어느 정도 유용한 건 맞지만, 생각보다 성능이 그렇게 시원찮은지는 모르겠다. 특히나 코드…
티앤미미 예약이 그렇게 힘들다는 티앤미미를 처남네가 운좋게 예약해서 어제 저녁 다녀왔다. 딤섬이 그렇게 맛있다고 하는데,…
아난티 부산 시설과 고객 서비스가 이렇게 극단적으로 다른 방향인 호텔이 있을까 싶다. 시설의 퀄리티는 5성급이라기에…
This website uses cookies.