[프로그래머스/2019 카카오/그리디] 무지의 먹방 라이브

무지의 먹방 라이브

* 효율성 테스트에 부분 점수가 있는 문제입니다.

평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 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_timeskresult

[3, 1, 2]

5

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번 음식부터 다시 먹기 시작하면 된다.

 

문제 해석(규칙 파악) & 사전지식(자료구조) 설명

 

이 문제를 가장 효과적으로 접근하기 위해서는 우선순위 큐를 활용해야 한다.

그런데 파이썬에서 우선순위 큐를 활용하는 방법에는 우선순위큐(Priority Queue)를 활용하는 방법과 힙(heap) 자료구조를 활용하는 방법이 있다.

 

그러기 위해서는 우선 힙 자료구조를 알 필요가 있다.

 

** 힙 자료구조 설명 **

 

- 힙 자료구조는 우선순위 큐를 구현하기 위하여 사용하는 자료구조 중 하나

- 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징

 

자료구조	추출되는 데이터
스택(Stack)	가장 나중에 삽입된 데이터
큐(Queue)	가장 먼저 삽입된 데이터
우선순위 큐(Priority Queue)	가장 우선순위가 높은 데이터

 

- 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용

ex) 여러개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 사용해야 하는 경우

- 대부분의 프로그래밍 언어에서 우선순위 큐 라이브러리를 제공함

 -> 직접 힙 자료구조부터 작성해서 우선순위 큐를 구현하지 않아도 됨

- 파이썬은 우선순위 큐가 필요할때 PriorityQueue 혹은 heapq를 사용할수 있음

- 일반적으로 heapq가 더 빠르게 동작하기 때문에 수행시간이 제한된 상태에서는 heapq를 사용하는 것을 권장함

- 우선순위 값을 표현할 때는 일반적으로 정수형 자료형의 변수가 사용됨

ex) 물건 정보가 있고, 이 물건 정보는 물건의 가치와 물건의 무게로만 구성된다고 가정

→ 모든 물건 데이터를 (가치, 물건)으로 묶어서 우선순위 큐 자료구조에 넣을 수 있음

이후에 우선순위 큐에서 물건을 꺼내게 되면, 항상 가치가 높은 물건이 먼저 나오게 됨

(우선순위 큐가 최대 힙으로 구현되어 있을 때를 가정한다. 최대 힙을 사용하는 경우, 값이 큰 데이터가 먼저 추출된다.)

- 대부분의 프로그래밍 언어에서는 우선순위 큐 라이브러리에 데이터의 묶음을 넣으면, 첫 번째 원소를 기준으로 우선순위를 설정

ex) 데이터가 (가치, 물건)으로 구성된다면 '가치' 값이 우선순위 값이 됨

- 우선순위 큐를 구현할 때는 내부적으로 최소 힙(Min Heap) 혹은 최대 힙(Max Hip)을 이용

최소 힙: 값이 가장 낮은 데이터가 먼저 삭제됨

최대 힙: 값이 큰 데이터가 먼저 삭제됨

- 파이썬 라이브러리에서는 기본적으로 최소 힙 구조를 이용

- 최소 힙을 최대 힙처럼 사용하기 위해서 일부러 우선순위에 해당하는 값에 음수 부호(-)를 붙여서 넣었다가, 나중에 우선순위 큐에서 꺼낸 다음에 다시 음수 부호(-)를 붙여서 원래의 값으로 돌리는 방식을 사용할 수 있다.

 

# 문제 해결 방법

 

아이디어 : 시간이 적게 걸리는 음식부터 확인하는 탐욕적인(Greedy) 접근 방식으로 해결할 수 있다.

모든 음식을 시간을 기준으로 정렬한 후, 시간이 적게 걸리는 음식부터 제거해 나간다.

이를 위해 우선순위 큐를 이용하여 구현할수 있다.

 

ex) 3개의 음식, K = 15초

- 1번 음식 : 8초 소요

- 2번 음식 : 6초 소요

- 3번 음식 : 4초 소요

 

(0) 초기 단계에서는 모든 음식을 우선순위 큐(최소 힙)에 삽입한다. 또한 마지막에는 K초 후에 먹어야 할 음식의 번호를 출력해야 하므로 우선순위 큐에 삽입할 때 (음식 시간, 음식 번호)의 튜플 형태로 삽입한다.

- 전체 남은 시간(K): 15초

- 남은 음식: 3개

 

(1) 첫 단계에서는 가장 적게 걸리는 음식인 3번 음식을 뺀다. 다만, 음식이 3개 남아있으므로 3 (남은 음식의 개수) x 4 (3번 음식을 먹는 시간) = 12를 빼야 한다. 3번 음식을 다 먹기 위해서는 12초가 걸린다는 의미이다. 결과적으로 전체 남은 시간이 15초에서 3초로 줄어들게 된다.

- 전체 남은 시간(K): 3초

- 남은 음식: 2개

 

- 먹은 음식들:

 

(2) 전체 남은 시간은 3초이고, 이번 단계에서는 2번 음식을 빼야 한다. 전체 음식이 2개 남아 있으므로 이번 단계에서 뺄 시간은 2 (남은 음식의 개수) x 2 (2번 음식을 다 먹는 시간) = 4초가 된다.

하지만 현재 전체 남은 시간이 3초인데, 이는 4보다 작으므로 빼지 않도록 한다.

따라서 '다음으로 먹어야 할' 음식의 번호를 찾아 출력하면 된다. 

매초 먹어야 할 음식들을 일렬로 나열해보자. 전체 남은 시간은 3초이므로 4번째 음식을 출력하면 정답이다.

 

import heapq

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) #남은 음식의 개수
    
    # sum_value + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식의 개수와 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]

 

- sorted()

# key 인자에 함수를 넘겨주면 해당 함수의 반환값을 비교하여 순서대로 정렬한다.

a = [(1, 2), (5, 1), (0, 1), (5, 2), (3, 0)]

b = sorted(a, key = lambda x : x[0])

# b = [(0, 1), (1, 2), (3, 0), (5, 1), (5, 2)]

c = sorted(a, key = lambda x : x[1])

# c = [(3, 0), (5, 1), (0, 1), (1, 2), (5, 2)]

 

# 비교할 아이템의 요소가 복수 개일 경우, 튜플로 그 순서를 내보내주면 된다.

# -를 붙이면, 현재와 반대차순으로 정렬된다.

d = sorted(a, key = lambda x : (x[0], -x[1]))

# d = [(0, 1), (1, 2), (3, 0), (5, 2), (5, 1)]