heapq

사용 이유

코테에서 주어진 변수의 범위가 적당할 경우에는 기본 자료형으로도 통과하지만

범위가 1~백만 정도로 커지면 처리 시간이 매우 길어져 효율성이 떨어지기 때문에

이를 해결하기 위해 heapq(힙)이라는 모듈을 사용

 

파이썬에서의 힙

- 파이썬에서 힙 모듈은 완전 이진 트리(binary tree) 기반의 최소 힙(min heap) 자료구조를 제공

- 최소 힙은 원소들이 항상 오름차순으로 정렬되며 항상 최소힙의 인덱스 0번의 위치에는 최솟값 데이터가 위치

 

힙 함수 종류

import heapq

 

- heappush(객체, 데이터) = 힙에 해당 데이터 추가

- heappop(객체) = 괄호안에  데이터를 입력하면 힙에서 해당 데이터 삭제 후 그 값을 출력

- heapify(리스트) = 리스트를 힙으로 변환

- heappushpop(객체, 데이터) = heappush 실행 후 heappop 실행

- heapreplace(객체, 데이터) = heappop 실행 후 heappush 실행

-> 모두 명령 처리후 자동으로 힙 구조에 맞게 데이터들이 재정렬되고 객체를 지정해주지 않고 메소드만 단독으로 입력해줘도 알아서 적용됨

- heapify()를 제외하고 나머지 함수는 시간복잡도가 O(logN) => heapify는 시간복잡도 O(N)

 

힙을 이용한 최솟값 출력

※  힙의 최솟값 데이터는 인덱스 0번을 이용하여 A[0]과 같이 불러오지만 인덱스 1번에 두번째로 작은 데이터, 인덱스 2번에 세번째로 작은 데이터가 있다는 보장이 없어서 두번째로 작은 데이터를 불러오려면 heappop(A[0])을 통해 최솟값 원소를 삭제한 후에 새로운 최솟값 데이터를 호출

-> n번째 최솟값을 구하려면 heappop(A[0]) n-1번 호출후 A[0] 출력

 

최대 힙

- 최대 힙을 만들려면 각 값에 대한 우선 순위를 구한 후, (우선 순위, 값) 구조의 튜플(tuple)을 힙에 추가하거나 삭제

- 힙에서 값을 읽어올 때는 각 튜플에서 인덱스 1에 있는 값을 취하면 됩니다. (우선 순위에는 관심이 없으므로)

 

★ 연습 문제 ★

https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

모든 음식의 스코빌 지수를 K 이상으로 만들때까지 다음과 같은 음식 믹싱과정(A) 반복

A : 섞은 음식 스코빌 지수 = 최소 스코빌 지수 + 두번째로 작은 스코빌 지수 X 2

모든 음식의 스코빌 지수를 K 이상으로 만들때까지 A를 반복한 횟수 출력

모든 음식의 스코빌 지수를 K 이상으로 만드는 것이 불가능하면 -1 출력

예시) solution([1, 2, 3, 9, 10, 12], 7) = 2

import heapq
def solution(scoville, K):
    heapq.heapify(scoville) # list -> heapq로 변환
    answer = 0
    while scoville[0] < K:
        a = []
        b = 0
        a.append(scoville[0])
        heapq.heappop(scoville) # 최솟값 삭제후 재배열
        a.append(scoville[0])
        heapq.heappop(scoville) # 최솟값 삭제후 재배열
        b = a[0]+a[1]*2
        heapq.heappush(scoville,b) # scoville에 b 추가후 재배열
        if len(scoville) == 1 and scoville[0] < K:
            answer = -1
            break
        else:
            answer += 1
        continue
    return answer