개발/알고리즘

[프로그래머스] 무지의 먹방 라이브

개발자_티모 2022. 11. 20. 14:53
반응형

아이디어 도출 방법

1. 먼저 효율성을 생각하지 않고 정확성 위주로 문제를 해결하려고 했다. 

  • 방송이 중단된 시간(k)만큼 돌면서 food_time[index]의 시간을 1초씩 감소시켜준다.
idx = 0
for i in range(k):
   remove_food_time(food_time[idx])
   idx += 1

2. 순차적으로 1초씩 줄이면 탈락하는 문제로 한번에 하나씩 삭제할 수 없을까 생각을 했다.

  1. 한 번에  FOOD_TIME [idx]의 시간을 0으로 만들 수 있다면 연산의 복잡도가 배열 길이에 따라 변한다.
  2. 그럼 어떤 Index가 먼저 0이 될까?
    1. 답은 간단하게 FOOD_TIME 중 최소 값이 먼저 사라진다
  3. 그럼 해당 Index를 0으로 만들 때 필요한 시간 계산은 어떻게 할 까?
    1. FOOD_TIME [index] * len(FOOD_TIME)을 하면 필요한 시간이 나온고 K에서 해당 시간을 차감해주면 된다.
    2. 또 다른 문제는 FOOD_TIME [index]의 시간이 K보다 크다면 K % len(FOOD_TIME)가 정답이 된다.

구현 포인트

1. 모든 배열의 시간을 더해도 K가 큰 경우에는 -1을 반환

2. 사용한 시간을 누적해야 한다. -> 다른 인덱스에는 해당 시간이 반영되지 않았기 때문이다.

코드

import heapq

def solution(food_times, k):
    if sum(food_times) <= k:
        return - 1

    previous = 0
    total = len(food_times)

    heap = []

    for i in range(len(food_times)):
        heapq.heappush(heap, [food_times[i], i])

    #previois를 꼭 더해주자
    while heap:
        min_time, idx = heapq.heappop(heap)
        min_time -= previous

        if min_time * total < k:
            previous += min_time
            food_times[idx] = 0

            k -= min_time * total
        else:
            need_forward = k % total
            forward = 0

            for idx in range(len(food_times)):
                if food_times[idx]:
                    if forward == need_forward:
                        answer = idx + 1   
                    forward += 1
            break
        total -= 1

    return answer

if __name__ == "__main__":
    food_times = [3, 1, 2]
    k = 5

    print(solution(food_times, k))

 

후기

좀 재미난 문제였다.  생각해보니 그리디 문제였다;

반응형