[python] 프로그래머스 Heap(힙) - 더 맵게 / heapq와 deque의 차이점

 

https://school.programmers.co.kr/learn/courses/30/lessons/42626?language=python3

프로그래머스

 

문제풀이. ( 비효율 적임)

def solution(scoville, K):  
    
    if min(scoville) >= K:
        return 0
    
    cnt = 0
    while len(scoville) != 1:
        i = min(scoville)
        scoville.remove(i)
        j = min(scoville)
        scoville.remove(j)
        
        k = i + j*2
        scoville.append(k)
        cnt += 1
        if min(scoville) >= K :
            return cnt
        
    
    return -1

 

 

이렇게 풀면 논리는 100%로 맞지만, 시간 효율성 측면에서 최악일 때는 O(n^2)이 나오기 때문에, 효율성에서는 모두 떨어졌다.

 

이때 heapq라는 개념을 알게 됐고,

이를 활용한 코드는

import heapq

def solution(scoville, K):  

    heapq.heapify(scoville)

    if scoville[0] >= K:
        return 0

    
    cnt = 0
    while len(scoville) != 1:
        i,j = heapq.heappop(scoville), heapq.heappop(scoville)
        heapq.heappush(scoville, i + j*2)
        cnt += 1
        if scoville[0] >= K :
            return cnt
        
    
    return -1

 

이것으로 시간 효율도가 O(n logn)으로 훨씬 효율적으로 변하게 된다.

heapq라는 module은 최소값을 찾는데, 최적화가 되어 있다!

 

 

---

deque / heapq 차이점

그런데, deque랑 heapq 랑 뭐가 다른지 궁금해서 찾아본 결과!

---

 

deque와 heapq는 둘 다 파이썬의 collections 모듈에서 제공하는 자료 구조이지만, 각각의 목적과 동작 방식이 다릅니다. 두 자료 구조의 차이점과 각자의 장단점에 대해 설명드리겠습니다.

 

deque (Double-Ended Queue):

 

1. 개념:

• deque는 양쪽 끝에서 데이터를 추가하거나 제거할 수 있는 자료 구조입니다.

• 스택(후입선출)과 큐(선입선출) 역할을 모두 할 수 있어 유연한 자료 구조입니다.

2. 주요 연산 및 시간 복잡도:

• append(): 오른쪽 끝에 데이터 추가 (O(1))

• appendleft(): 왼쪽 끝에 데이터 추가 (O(1))

• pop(): 오른쪽 끝에서 데이터 제거 (O(1))

• popleft(): 왼쪽 끝에서 데이터 제거 (O(1))

3. 사용 사례:

• 스택과 큐의 역할을 모두 수행할 때 유용합니다.

• 양쪽 끝에서의 삽입과 삭제가 빈번하게 발생하는 상황에 적합합니다.

4. 특징:

• deque는 요소를 추가하거나 제거할 때 리스트보다 빠르지만, 특정 위치에서 요소를 검색하거나 제거하는 것은 비효율적입니다(O(n)).

 

heapq (Heap Queue):

 

1. 개념:

• heapq는 힙 자료 구조를 구현한 모듈로, 기본적으로 최소 힙으로 동작합니다. 힙은 완전 이진 트리 형태를 유지하며, 루트 노드가 항상 최소값(또는 최대값)을 갖습니다.

• 데이터 삽입 및 삭제 시 자동으로 정렬 상태를 유지합니다.

2. 주요 연산 및 시간 복잡도:

• heappush(heap, item): 힙에 요소 추가 (O(log n))

• heappop(heap): 힙에서 최소값 제거 및 반환 (O(log n))

• heapify(iterable): 기존 리스트를 힙 구조로 변환 (O(n))

3. 사용 사례:

• 우선순위 큐 구현, 가장 작은 값을 빠르게 찾고 삭제해야 하는 상황에 적합합니다.

• 다익스트라 알고리즘, 작업 스케줄링 등에서 자주 사용됩니다.

4. 특징:

• 힙은 항상 정렬 상태를 유지하므로, 삽입과 삭제가 자동으로 정렬된 상태에서 이루어집니다.

• 최소값(또는 최대값)을 효율적으로 관리할 수 있습니다.

 

비교: deque vs heapq:

특징	deque	heapq
주요 목적	양쪽 끝에서 삽입/삭제	최소값(또는 최대값) 관리
시간 복잡도	양쪽 끝 삽입/삭제 O(1)	삽입/삭제 O(log n)
정렬 상태	자동 정렬되지 않음	자동 정렬(최소 힙) 유지
사용 사례	스택, 큐 구현	우선순위 큐, 최소값 관리
특성	선형 구조, 정렬 필요 시 O(n)	완전 이진 트리 구조, 정렬 자동

 

결론:

• deque는 스택과 큐 역할을 효율적으로 수행할 수 있지만, 정렬된 상태를 유지하지 않기 때문에 최소값이나 최대값을 관리하는 데는 적합하지 않습니다.

• heapq는 최소값(또는 최대값)을 효율적으로 관리할 수 있는 자료 구조로, 정렬 상태를 유지하면서 삽입과 삭제가 이루어져 우선순위 큐 등의 문제에 적합합니다.