PROGRAMMERS Python Lv2. 더 맵게

이번 문제는 더 맵게이다.

나의 코드는 다음과 같다.

import heapq
def solution(sco, K):
    heapq.heapify(sco)
    cnt = 0
    while len(sco) >= 2:
        min_ = heapq.heappop(sco)
        if min_ >= K:
            return cnt
        else:
            min2_ = heapq.heappop(sco)
            heapq.heappush(sco, min_ + (min2_ * 2))
            cnt += 1
    if sco[0] > K:
        return cnt
    else:
        return -1

위 문제는 Heap 알고리즘에 해당해서 우선 heapq에 대해 검색해보았다.

최댓값과 최솟값을 찾기에 매우 유용한 알고리즘인데, 항상 맨 처음 원소는 가장 작은 노드가 오고,

인덱스가 k일 때 수는 2k+1,2K+2인 수보다 작게끔 만들어진다.(최소힙의 경우)

haepify를 통해, 리스트를 힙구조로 만들어 줄 수 있다. 그렇게 하면 힙 구조로 정렬된다.

heappop과 heappush는 기존의 pop과 push와 유사한 기능을 하는데, push의 경우 리스트를 인자로 부여해야한다.

문제 풀이

1. 주어진 리스트를 힙구조로 변환한다(heapify)

2. cnt = 0으로 하고, 나중에 답으로 반환한다.

3. heappop을 통해 최솟값을 추출한다. 이미 최솟값이기 때문에 K보다 크다면 바로 0인 cnt를 반환한다.

4. 최솟값을 제외했으니 다음에 추출하는 원소가 남아있는 힙 자료형 중 제일 작은 값이다.

5. 이를 heappush를 통해 주어진 계산식에 맞춰 넣어준다.

6. 만약 이렇게 변환했는데도 인덱스 0의 값이 K보다 작다면 -1을 반환한다.