[프로그래머스] 무지의 먹방 라이브
생각흐름
- 이전에 내가 못 풀었던 문제이다.
- k값을 어떤 방식으로 빼느냐가 관건이다.
- 배열 인덱스를 잘 다뤄야 하는 문제이다.
- 음식들을 다 먹게 되는 사이클의 크기만큼 줄여나가보도록 하자
- 사이클이 너무 크다.
- 사이클이 너무 큰데다가, 남은 음식을 몇 바퀴 돌아야 k값이 0이 되는 경우를 해결 못함
- 2번의 경우를 캐치하지 못한다면 어떤 곳에선 -1이 나와버리는 불상사 -> 정확성 실패
- 음식들 길이만큼의 사이클로 줄여보자
- 정확성은 맞는다.
- 효율성에서 실패한다.
- 4번과 5번을 결합하자.
- 4번대로 하다가 k값이 부족해지면 5번을 돌린다.
- 효율성에서 하나가 실패한다...
- 5번을 돌릴 때, for문으로 하는 게 아니라 나눠주자. k는 k를 남은 음식 수로 나눈 나머지요, 바퀴 수는 k를 그 몫이다.
- 효율성은 통과하나 정확성에서 틀린다.
- 바퀴 수, 즉 현재 추가적으로 더 먹고 있는 음식의 양은 천장으로 구해야 한다. 2바퀴를 돌 수 있는데 3바퀴는 못 돈다면 무지는 현재 추가적으로 3의 양을 먹으려 하고 있다.
풀이
싸이클의 크기를 최대화 해서 k
값을 줄여나가다가
마지막 순간에만 배열을 돌아야 하는 문제다. (배열을 하나하나 도는 것을 최소화하는 것이 관건)
먼저 음식의 양을 카운트하고 이를 양의 오름차순으로 정렬한다.
이 순서대로 해당 음식을 전부 먹어가기 때문이다. (양이 4인 음식은 양이 10인 음식보다 빨리 없어진다)
이를 food_cnt
라 하자.
정렬한 후, 그 음식이 모두 비워지게 되는 싸이클의 크기, to_remove
를 구한다.
정렬된 배열은 (음식의 양, 등장 횟수)
들로 이루어졌다.
i
번째로 적은 양의 음식을 모두 먹어버린다고 생각하자.
현재 먹을 음식의 양은 food_cnt[i][0]
,
그 개수는 food_cnt[i][1]
,
남은 음식의 수를 food_left
라 하자.
그리고 현재 돌면서 여태 먹은 음식의 양을 food_ate
라 하자.
to_remove
는 현재 to_eat (=지금 먹을 음식의 양) * food_left
이다.
to_eat
은 food_cnt[i][0] - food_ate
이다.
예를 들어, 원래 양이 4인 음식을 끝내버릴 차례인데
여태 음식을 앞에서 각각 2만큼 먹었다고 한다면 지금은 2만큼만 먹어도 그 음식을 모두 먹을 수 있다.
그대로 k
값을 줄여나간다. (k -= to_remove
)
food_left
는 food_cnt[i][1]
만큼 줄어들고
food_ate
은 to_eat
만큼 늘어난다.
food_ate
는 여태 먹은 음식의 총합이 아닌 각 음식에서 대해서 먹은 양이라는 것에 주목하자.
만약에 k - to_remove
가 음수가 된다면 (해당 음식을 해치우기 이전에 방송이 종료된다면)
그때부터는 사이클의 크기를 남은 음식을 1씩 깎는 주기로 바꾼다.
food_left
만큼 깎아나간다면 k
를 food_left
로 나눈 나머지가 우리가 배열을 돌아야 할 최소 횟수이다.
이렇게 되면 현재 먹고 있는 음식의 양은 k
를 food_left
로 나눈 몫이며, 나머지가 1이라도 있다면 1을 추가하게 된다.
예를 들자면 만일 k=5
이고 food_left
가 3이라고 쳤을 때,
무지는 세 음식에 대해서 1씩 먹을 수 있다.
그러고도 모자라 앞의 두 음식에서 1씩 더 먹을 수 있다.
즉 마지막에 방송이 중지됐을 땐, 남은 음식들 중에서 도합 2만큼 먹던 중이던 것이다.
따라서 무지는 ceil(k / 남은 음식의 수)
을 추가로 더 먹을 수 있다.
이를 able
이라고 하자.
이는 무지가 음식들을 돌면서 먹을 수 있는 최대치이다.
무지가 현재 남은 음식들을 k // 남은 음식의 수
바퀴 돌면서 음식을 먹었고,
우리는 미처 다 돌지 못하는 나머지를 직접 돌아보는 것이라고 이해하면 편하다.
이제 k
를 1씩 감소시키며 배열을 탐색할 차례이다.
음식이 남았는지 아닌지를 알기 위해선, 배열(food_times
)의 원소가 food_ate + able
보다 크거나 같은지를 보면 된다.
같다면, 이번 차례에서 다 먹게 되는 음식인 것이다.
크다면, 그렇게 먹어도 아직 다 먹지 못한 음식이다.
작다면 돌기 전에 이미 다 먹은 음식이다.
크거나 같으면 k
를 감소시킨다.
그러다 k
가 0이 될 때, k
초 후 먹을 음식의 인덱스를 반환한다.
만약 위의 전체적인 과정에서 단 한 번도 k
값이 음수가 되는 경우가 없다면
이는 k
초가 지나면 음식들을 이미 다 먹었다는 말이므로 -1를 반환한다.
밑은 예시를 그림으로 나타낸 것이다.
코드
from collections import Counter
from math import ceil
def solution(food_times, k):
n = len(food_times)
# food_cnt[i] = (i 번째로 적은 음식의 양, 같은 양을 가지는 음식의 개수)
food_cnt = sorted(list(Counter(food_times).items()))
# 현재 먹은 각 음식의 양
food_ate = 0
# 남은 음식 수
food_left = n
for i in range(len(food_cnt)):
# i 번째로 적은 음식의 현재 잔량
to_eat = food_cnt[i][0] - food_ate
# i 번째로 적은 음식을 아예 비워버리기 위해 지나야 하는 시간
to_remove = to_eat * food_left
# 아예 비우진 못한다면
if k - to_remove < 0:
# 현재 남아있는 음식들을 돌 수 있는 바퀴 수 = 더 비울 수 있는 각각의 음식의 양
able = ceil(k / food_left)
# able 바퀴 씩 돌고 남은 k
k %= food_left
# 현재 다 먹은 각 음식의 양
now_eaten = food_ate + able
for l in range(n):
# 음식의 양이 현재 먹은 양보다 크거나 같다면 (= 아직 남아있다면)
if food_times[l] >= now_eaten:
# k 초 후 먹을 음식 발견
if k == 0:
return l + 1
k -= 1
# i 번째로 적은 음식을 아예 비워버림
k -= to_remove
# 지금까지 먹은 각 음식의 양 추가
food_ate += to_eat
# 남은 음식 개수 줄이기
food_left -= food_cnt[i][1]
return -1
Author And Source
이 문제에 관하여([프로그래머스] 무지의 먹방 라이브), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jkjan/프로그래머스-무지의-먹방-라이브저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)