[Heap] 이중우선순위큐 - Python

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/42628?language

프로그래머스

 

[문제 간단 요약]

 

• 큐에 숫자를 삽입하거나 최댓값/최솟값을 삭제하는 연산이 주어진다.
• 모든 연산을 수행한 후, 큐가 비어 있지 않다면 [최댓값, 최솟값]을 반환하고, 비어 있으면 [0, 0]을 반환한다.

 

 

[문제 해결 방안]

✅ Heap

• 파이썬의 heapq는 최소 힙만 지원하므로,
  • 최솟값 관리: 일반 힙(li)
  • 최댓값 관리: 음수 변환하여 힙(revert_li)
• 삽입 시 두 힙에 모두 넣어 동기화
• 삭제 시 조건에 맞게 하나에서 heappop 후, 다른 힙에서도 해당 원소를 remove로 제거
• 마지막에 힙이 비었는지 여부를 확인 후 결과 반환

 

[문제 해결 코드 - python]

import heapq

def solution(operations):
    li = []
    revert_li = []
    for operation in operations:
        if operation[0] == 'I':
            heapq.heappush(li, int(operation[2:]))
            heapq.heappush(revert_li, -int(operation[2:]))
        elif len(li) != 0 and operation[0] == 'D':
            if operation[1:] == ' -1':
                chk_num = heapq.heappop(li)
                revert_li.remove(-chk_num)
            elif operation[1:] == ' 1':
                chk_num = heapq.heappop(revert_li)
                li.remove(-chk_num)
    if len(li) == 0:
        answer = [0,0]
    elif len(li) == 1:
        num = heapq.heappop(li)
        answer = [num,num]
    else:
        answer = [-heapq.heappop(revert_li), heapq.heappop(li)]
    return answer

 

[코드 개선점]

• list.remove() 비효율성
  • remove()는 O(n) → 연산 횟수가 많아질수록 성능 저하
  • 개선: lazy deletion (삭제된 원소 표시만 하고 실제 pop 시 제거)
• 중복 원소 처리
  • 같은 값이 여러 번 들어간 경우, remove()는 첫 번째 원소만 제거
  • 다른 힙에 동일 값이 여러 개 들어 있으면 싱크가 깨질 수 있음
• 코드 가독성
  • "I" 연산 처리 시 int(operation[2:]) 중복 → 한 번만 파싱
  • "D -1", "D 1" 비교 시 문자열 slicing 대신 split() 활용 가능
• 최종 결과 반환 시 부작용
  • heapq.heappop()을 사용해 실제 힙을 꺼내므로, 결과를 반환한 뒤 원본 상태가 사라짐
  • 문제 풀이에선 상관없지만, 함수 호출 후 힙을 유지해야 한다면 부적절

[문제 해결 코드 - python]

import heapq

def solution(operations):
    min_h, max_h = [], []
    exist = {}  # lazy deletion 관리용 딕셔너리

    def clean(heap, is_max=False):
        # 유효하지 않은 값 제거
        while heap and exist.get((val := (-heap[0] if is_max else heap[0])), 0) == 0:
            heapq.heappop(heap)

    for op in operations:
        if op[0] == 'I':
            num = int(op[2:])
            heapq.heappush(min_h, num)
            heapq.heappush(max_h, -num)
            exist[num] = exist.get(num, 0) + 1
        elif op == "D -1":
            clean(min_h)
            if min_h:
                val = heapq.heappop(min_h)
                exist[val] -= 1
        elif op == "D 1":
            clean(max_h, True)
            if max_h:
                val = -heapq.heappop(max_h)
                exist[val] -= 1

    clean(min_h)
    clean(max_h, True)

    if not min_h or not max_h:
        return [0, 0]
    return [-max_h[0], min_h[0]]