효율성이 얼마나 중요한지 알게해주는 유명한 문제라고한다.
알고리즘 코스를 듣다가 이코테 책에 있던 문제를 풀어보았었는데
처음엔 로직이 그리 어렵지 않네? 라고 착각했었다.
답이 나오는 로직이 문제가 아니라 효율성있게 코드를 작성하는 것이 문제였다.
문제를 보면,
무지의 먹방 라이브
- 효율성 테스트에 부분 점수가 있는 문제입니다.
평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다.
그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다.
회전판에 먹어야 할 N 개의 음식이 있다.
각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다.
무지는 다음과 같은 방법으로 음식을 섭취한다.
무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.
마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.
무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다.
다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다.
회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다고 가정한다.
무지가 먹방을 시작한 지 K 초 후에 네트워크 장애로 인해 방송이 잠시 중단되었다.
무지는 네트워크 정상화 후 다시 방송을 이어갈 때, 몇 번 음식부터 섭취해야 하는지를 알고자 한다.
각 음식을 모두 먹는데 필요한 시간이 담겨있는 배열 food_times, 네트워크 장애가 발생한 시간 K 초가 매개변수로 주어질 때 몇 번 음식부터 다시 섭취하면 되는지 return 하도록 solution 함수를 완성하라.
제한사항
food_times 는 각 음식을 모두 먹는데 필요한 시간이 음식의 번호 순서대로 들어있는 배열이다.
k 는 방송이 중단된 시간을 나타낸다.
만약 더 섭취해야 할 음식이 없다면 -1을 반환하면 된다.
정확성 테스트 제한 사항
food_times 의 길이는 1 이상 2,000 이하이다.
food_times 의 원소는 1 이상 1,000 이하의 자연수이다.
k는 1 이상 2,000,000 이하의 자연수이다.
효율성 테스트 제한 사항
food_times 의 길이는 1 이상 200,000 이하이다.
food_times 의 원소는 1 이상 100,000,000 이하의 자연수이다.
k는 1 이상 2 x 10^13 이하의 자연수이다.
입출력 예
food_times = [3, 1, 2]
k = 5
result = 1
입출력 예 설명
입출력 예 #1
0~1초 동안에 1번 음식을 섭취한다. 남은 시간은 [2,1,2] 이다.
1~2초 동안 2번 음식을 섭취한다. 남은 시간은 [2,0,2] 이다.
2~3초 동안 3번 음식을 섭취한다. 남은 시간은 [2,0,1] 이다.
3~4초 동안 1번 음식을 섭취한다. 남은 시간은 [1,0,1] 이다.
4~5초 동안 (2번 음식은 다 먹었으므로) 3번 음식을 섭취한다. 남은 시간은 [1,0,0] 이다.
5초에서 네트워크 장애가 발생했다. 1번 음식을 섭취해야 할 때 중단되었으므로, 장애 복구 후에 1번 음식부터 다시 먹기 시작하면 된다.
처음부터 효율성 부분에 점수가 있는 문제라고 하는데
부분점수라고 해석이 되었었는데 그냥 효율성이 전부인 문제라고 생각한다.
답이 중요한게 아니라 그 답을 효율성 있게 이끌어내야한다.
for문을 돌면서 한바퀴당 1초를 잡고 각 음식을 순서대로 1씩 차감하면 값은 멀쩡하게 잘 나오게 되어있다.
그리 어렵지 않다.
하지만,
반복문1번 당, 1초로잡게되면 무의미한 반복을 계속하게 된다.
어떻게 해야 효율적으로 더 적게 반복문을 돌면서 정확한 결과값을 가져올 수 있을까?
특정 구간의 반복을 미리 계산해서 반복할 순 없을까?
하나의 음식을 다 먹을때까지 몇바퀴를 돌아야 할까?
가장 빨리 먹는 음식은 몇번이며, 그 음식을 다 먹을 때까지는 몇바퀴를 돌아야 할까?
예시에서 나온 [3,1,2]의 경우, 1번 idx의 음식은 1초면 다 먹는다.
0~1초에 0번 idx 음식을 먹고, 1~2초에 1번 idx음식을 먹는다.
그럼 1번 idx음식을 다 먹는다.
1초 단위로 보지말고, 한싸이클 단위로 본다면?
첫 사이클을 다 돌았을 때, 음식이 하나 줄어들고
음식이 줄어들기 전까지는 반복문 1번으로 계산이 가능하다.
1번 idx의 음식은 다 먹는다.
0번 idx의 음식은 2초간 더 먹어야하고
2번 idx의 음식은 1초간 더 먹어야 한다.
그럼 하나의 음식을 다 먹을때 까지 몇 사이클을 돌아야 하며,
그 때까지 몇 초가 걸리는지 1초당 1반복이 아니라, 1반복에 음식1개 다 먹을때까지이다.
그렇게 3초를 1반복으로 계산하게 되고
6초를 2반복
9초를 3반복으로 계산하게 되는데,
k의 값은 5초 이므로
1반복으로 3초까지 계산하고 2초가 남는다.
완벽하게 다 순환하지 못하고 남은 시간은 어떻게 해야할까?
남은 시간은 1초씩 반복문을 돌며 값을 가져오는것이 아니라
그냥 계산을 하면 된다.
남은 순서를 (k초까지 남은 시간)/(음식갯수) 로 계산하여
음식의 idx를 계산한다.
그리고 음식의 번호를 리턴하면 된다.
코드
import heapq
def solution(food_times, k):
if sum(food_times) <= k:
return -1
tot_time = 0
cycle = 0
h=[]
for i, food_times in enumerate(food_times):
heapq.heappush(h, (food_times, i+1))
print("h",h)
num_foods = len(h)
while k > tot_time + ((h[0][0] - cycle) * num_foods):
tot_time += (h[0][0] - cycle) * num_foods
cycle += (h[0][0] - cycle)
print("tot!", tot_time)
heapq.heappop(h)
num_foods-=1
remain = sorted(h, key=lambda x: x[1])
print("remain", k - tot_time, remain)
return remain[(k - tot_time) % num_foods][1]
if __name__ == '__main__':
l = [3,1,2]
n = 5
res = solution(l,n)
print("res",res)