[이것이 코딩테스트다] 무지의 먹방라이브

문제

회전판에 먹어야할 n개의 음식이 있고, 각 음식은 1부터 n까지의 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다.

무지는 다음과 같은 방법으로 음식을 섭취

 

1. 무지는 1번부터 음식을 먹고, 회전판은 번호가 증가하는 순서대로 음식을 무지앞으로 갖다놓음

2. 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 다시 무지한테

3. 무지는 음식하나를 1초동한 섭취한 후 남은 음식을 그대로 두고 다음 음식을 섭취

3. 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다.

 

먹방을 시작한지 k초 후 방송이 잠시 중단하고, 몇 번 음식부터 섭취해야하는지 알고자 한다.

각 음식을 모두 먹는데 필요한 시간이 담겨있는 배열 food_times, 네트워크 장애가 발생한 k초가 매개변수로 주어질 때 몇번 음식부터 다시 섭취하면 되는지 return하세요.

 

제한 사항

• food_times는 각 음식 모두 먹는데 필요한 시간이 음식의 번호 순서대로 들어있는 배열
• k는 방송이 중단된 시간
• 만약 더 섭취할 음식이 없다면 -1 반환

정확성 제한사항

• food_times의 길이는 1이상 2000이하
• food_times 원소는 1이상 1000이하
• k는 1이상 2000000이하의 자연수

효율성 제한사항

• food_times의 길이는 1이상 200000이하
• food_times의 원소는 1이상 100000000이하의 자연수
• k는 1이상 2x10^13이하의 자연수

 

입력 예시

[3,1,2] 5

출력 예시 

 

해결 방법

시간이 적게 걸리는 음식부터 확인하는 방식으로 접근해야한다.

시간이 걸리는 순서대로 정렬을 한 뒤 시간이 적게 걸리는 음식부터 제거해 나가는 방식을 이용해야한다.

에를 들어

1번 음식이 8초, 2번음식이 6초, 3번음식이 4초 소요된다고 해보자.

음식 번호와 시간을 같이 담아서 배열에 담은후 정렬을 하면

[[3,4],[2,6],[3,8]] 

이 된다.

 

k는 15초 일때

3번 음식을 다 먹는 시간은 4(3번 음식을 먹는데 소요된 시간)*3(남은 음식의 갯수)=12이 걸릴 것이다.

전체 남은 시간은 3초이고 이번 단계에서 2번 음식을 빼야한다. 전체 음식이 2개 남아있으므로 이번 단계에서 뺄 시간은 2(남은음식의 갯수)*2(2번음식을 다 먹는 시간)=4초가 되는데, 남은 시간 3초보다 더 크므로 빼지 않도록 한다.

따라서 음식을 빼지 않고 다음 먹을 음식을 출력하면 된다.

 

코드

from collections import deque
def solution(food_times, k):
    if sum(food_times)<=k :
        return -1
    array=[]
    answer=0
    for i, v in enumerate(food_times) :
        array.append([i+1, v])
    array=sorted(array, key=lambda x : x[1])
    q=deque(array)
    
    #먹기위해 사용한 시간
    sumv=0
    #직전에 다 먹은 음식 시간
    prev=0
    length=len(food_times) #남은 음식 갯수
    
    while sumv+((q[0][1]-prev)*length) <=k :
        now=q.popleft()[1]
        sumv+=(now-prev)*length
    
        length-=1
        prev=now
    
    result=sorted(q, key=lambda x:x[0])
    return result[(k-sumv)%length][0]
    
    
    
    return answer

※<이것이 취업을 위한 코딩테스트다 (나동빈 저)>를 참고하여 작성된 게시글입니다.