[Python] 힙(heapq) 정리

https://youtu.be/AjFlp951nz0?si=K7SUuD9gkoN4fs8F

 

이 글은 '이것이 취업을 위한 코딩테스트다 with python'을 읽고 정리한 것입니다.

 

파이썬에는 힙(heapq) 기능을 위해 heapq 라이브러리를 제공한다. heapq는 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 우선순위 큐 기능을 구현하고자 할 때 사용된다.

 

힙에 원소를 삽입할 때는 heapq.heappush() 메서드를 이용하고, 힙에서 가장 작은 원소를 꺼내고자 할 때는 heapq.heappop() 메서드를 이용한다.

 

힙 정렬

1. 오름차순

import heapq

def heapsort(iterable):
    h = []
    result = []
    
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h,value)
        
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for _ in range(len(h)):
        result.append(heapq.heappop(h))
    return result

result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(result)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

2. 내림차순

import heapq

def heapsort(iterable):
    h = []
    result = []
    
    # 모든 원소를 힙에 삽입
    for value in iterable:
        heapq.heappush(h, -value)
        
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for _ in range(len(h)):
        result.append(-heapq.heappop(h))
    return result

result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(result)

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

 

---

가장 기본(?)문제

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

프로그래머스

 

이 문제의 경우 스코빌의 가장 작은값 두개를 조건에 따라 계산한 뒤 정렬에 맞게 리스트에 넣기 때문에 힙 문제이다.

 

import heapq
def solution(scoville, K):
    answer = 0
    h = []
    
    for value in scoville:
        heapq.heappush(h, value)
        
    while h[0]<K:
        
        if len(h)<2:
            return -1
        
        first = heapq.heappop(h)
        second = heapq.heappop(h)
        new = first + (second*2)
        heapq.heappush(h, new)
        answer += 1
    return answer

 

또한, 주어진 scoville이 처음부터 원소가 2개만 존재할 수 있기 때문에 if문을 가장 먼저 써야한다!

---

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

프로그래머스

 

 

import heapq
def solution(operations):
    answer = []
    
    for ope in operations:
        if "I" in ope:
            heapq.heappush(answer, int(ope[2:]))
        elif ope=="D -1":
            if answer:
                heapq.heappop(answer)
        elif ope=="D 1":
            if answer:
                answer.pop(answer.index(max(answer)))
    
    if len(answer)==0:
        return [0,0]
    else:
        return [max(answer), min(answer)]

 

3단계이지만 answer.pop()를 제외하고는 다 맞췄다.....ㅎ

 

---

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

프로그래머스

 

이 문제의 경우 종료시점을 기준으로 정렬이 필요하다.

 

작업 소요시간에 따라 넣은 뒤, 작업 시간 소요시간에 따라 정렬된다.