무지의 먹방 라이브 [그리디]

def solution(food_times, k):
    answer = 0
    time=0
    while True:
        if sum(food_times)==k:
            return -1
        
        for i in range(len(food_times)):
            if food_times[i]>0:
                food_times[i]-=1 # 음식을 1만큼 빼줌
                time+=1 # 1초에 음식 하나씩 섭취
            
            if time==k+1: # 멈춘 시간 다음에 먹는 음식 체크
                answer=i+1
                return answer

• 이중 반복문 때문에 시간 초과 오류 뜸
• 프로그래머스 37.5점..
• 효율성 0점

2번째 풀이: 오류 잡음

# 회전판 N개의 음식.
# 음식에는 1~N까지 번호
# 음식은 로테이션을 돎
# 1초 동안 섭취 후 남은 음식 두고 그 다음 움식 섭취.
# 먹방 한 후 k초 간 방송 중단. 몇번 음식부터 섭취하는지?
# 섭취해야 할 음식 X 면 -1 반환 (리스트 비어있을 때)
def solution(food_times, k):
    answer = 0
    time=0
    if sum(food_times)<=k:
        return -1

    while True:
       
        for i in range(len(food_times)):
            if food_times[i]>0:
                food_times[i]-=1 # 음식을 1만큼 빼줌
                time+=1 # 1초에 음식 하나씩 섭취
            
            if time==k+1: # 멈춘 시간 다음에 먹는 음식 체크
                answer=i+1
                return answer

• 네트워크 오류가 생기기 전 음식을 다 먹는다면 남은 음식은 없고, 이때 -1을 반환한다.
• 프로그래머스 42.9 (효율성 0)

효율적 풀이 : 힙큐 활용

import heapq
# k는 방송 중단 시간, food_times 는 음식의 번호 순서대로 들어있는 배열

def solution(food_times,k):

    # 전체 음식을 먹는 시간보다 k가 크거나 같으면 -1
    if sum(food_times)<=k:
        return -1
    #시간이 작은 음식부터 빼야함 (우선순위 큐 이용)
    q=[]
    for i in range(len(food_times)):
        # (음식시간, 음식 번호) 형태로 우선순위 큐에 삽입
        # 시간이 작은 음식부터 빼야하므로 우선순위 큐를 사용
        heapq.heappush(q,(food_times[i],i+1))

    sum_value=0 # 먹기 위해 사용한 시간
    previous=0 # 직전에 다 먹은 음식 시간

    length=len(food_times) # 남은 음식 개수

    # (현재 음식 시간-이전 음식 시간) * 남은 음식의 개수 와 k 값의 비교
    # k 보다 작다는 것은 음식을 뺄 수 있다는 뜻
    while sum_value+((q[0][0]-previous)*length) <=k:
        now=heapq.heappop(q)[0]
        sum_value+=(now-previous)*length
        length-=1 # 다 먹은 음식은 전체 음식 개수에서 제외함.
        previous=now # 이전 음식 시간을 재설정.
        
    result = sorted(q, key = lambda x: x[1]) # 음식 번호 기준으로 정렬하여 저장
    return result[(k - sum_value) % length][1]

1.

먹기 위해 사용한 시간(0) + ((현재 음식 시간(4) - 이전 음식 시간(0)) 남은 음식 개수(3)) <= 15
-> 12 <= 15 가 성립하므로 현재 음식을 뺄 수 있다. 그러면 now = 4, sum_value = (4 - 0) * 3 = 12, length = 3 - 1 = 2, previous = 4 가 된다.

2.

먹기 위해 사용한 시간(12) + ((현재 음식 시간(6) - 이전 음식 시간(4)) * 남은 음식 개수(2)) <= 15 -> 16 <= 15 가 성립하지 않으므로 while문을 빠져나온다.

result = [(8,1), (6,2)] 가 되고, result[(15 - 12) % 2][1] = result[1][1] = 2가 리턴

참고
https://soohyun6879.tistory.com/142 [코딩기록]