그리디 알고리즘 : 무지의 먹방 라이브 - 파이썬 (python)

programmers.co.kr/learn/courses/30/lessons/42891

코딩테스트 연습 - 무지의 먹방 라이브

* 힙 설명

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

* 방법1

아이디어: 시간이 적게 걸리는 음식부터 확인하는 탐욕적(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)]

 

 

github.com/501501/codingTest/commit/1ae94b6a3102a65ce851564c9a3872a9f184a5d7

#11-06 · 501501/codingTest@1ae94b6