카카오 블라인드 채용

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

admin

Recent Posts

2024년 11월 17일 일요일 – 서울 생활 129주차

괌여행 아내와 함께 괌으로 여행을 갔다. 출산 이후로 둘만 가는 첫 여행이다. 하와이가 일본인들이 많이…

3일 ago

2024년 11월 3일 일요일 – 서울 생활 127주차

반복적인 일상 매일 아침 일어나 회사에 출근하고, 저녁을 먹고 돌아오는 일상의 반복이다. 주말은 가족을 보러…

3주 ago

2024년 10월 6일 일요일 – 서울 생활 123주차

Planning A well-structured plan has the following characteristics:   First, the ultimate vision you aim to…

2개월 ago

2024년 9월 29일 일요일 – 서울 생활 122주차

English The most common problem for English learners like myself is that we often use…

2개월 ago

2024년 9월 22일 일요일 – 서울 생활 121주차

추석 추석을 맞아 친가 외가 처가 어르신들을 모두 뵙고 돌아왔다. 아이가 태어난지는 좀 됐지만 한국에서…

2개월 ago

2024년 9월 8일 일요일 – 서울 생활 119주차

주말 이번주는 아내가 올라와서 주말을 함께 보냈다. 둘만 밥도 먹고 뮤지컬도 보고, 모임도 나가고 집에서…

2개월 ago

This website uses cookies.