프로그래머스

프로그래머스 이중우선순위큐 풀이: 두 힙과 지연 삭제

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

  • 문제: 이중우선순위큐
  • 출처: 프로그래머스 코딩테스트 연습, 힙(Heap)
  • 자체 판단 난이도: Level 3

최솟값과 최댓값을 모두 빠르게 삭제해야 하므로 두 방향의 우선순위 큐를 함께 관리해야 한다. 두 힙의 동일한 원소를 안전하게 동기화하는 지연 삭제까지 필요하고, 연산 수가 최대 1,000,000개이므로 Level 3으로 판단했다.

1. 문제 요약

각 명령은 다음 중 하나다.

  • I 숫자: 숫자를 큐에 삽입한다.
  • D 1: 현재 큐에서 최댓값 하나를 삭제한다.
  • D -1: 현재 큐에서 최솟값 하나를 삭제한다.

모든 명령을 처리한 뒤 큐가 비어 있으면 [0, 0], 비어 있지 않으면 [최댓값, 최솟값]을 반환한다. 빈 큐에서 삭제하는 명령은 무시하며, 같은 값이 여러 개 있으면 그중 하나만 삭제한다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

Python의 heapq는 최소 힙만 제공하므로 다음 세 가지 상태를 관리한다.

  • min_heap: 값을 그대로 넣어 최솟값을 확인한다.
  • max_heap: 값의 부호를 바꾸어 넣어 최댓값을 확인한다.
  • counts: 각 값이 실제 큐에 몇 개 남아 있는지 기록한다.

삽입할 때 두 힙에 모두 값을 넣고 counts[value]를 1 증가시킨다. 삭제할 때는 선택한 힙의 최상단을 확인한다. 그 값의 counts가 0이면 반대쪽 힙에서 먼저 삭제된 오래된 복사본이므로 버린다. 살아 있는 값이 최상단에 도착하면 counts를 1 감소시키고 해당 힙에서 꺼낸다.

두 힙에 같은 값이 중복되어 있어도 counts가 남은 개수를 나타내므로 정확히 하나만 삭제할 수 있다. 별도의 전체 동기화나 정렬 없이 각 원소는 각 힙에서 많아야 한 번만 버려진다.

지연 삭제에서 유지할 불변식

counts가 실제 큐에 남은 원소를 결정하고, 두 힙은 그 원소들의 후보를 담는다. 한쪽에서 값을 삭제하면 반대쪽 힙의 복사본은 즉시 찾아 지우지 않고 stale 상태로 둔다. 그 값이 나중에 힙의 top에 왔을 때 counts[value] == 0을 확인하고 제거하면 된다.

예를 들어 I 5, I 1, D -1을 처리하면 실제 큐에는 5만 남지만 최대 힙 안에는 1의 오래된 복사본도 남아 있다. 이때 counts[1] == 0이므로 최대 힙에서 1이 top이 되는 순간 정리한다. 삭제한 값을 상대 힙에서 즉시 찾아 제거하거나 힙 전체를 다시 만들 필요가 없다.

삭제 전에는 선택한 힙의 top에서 stale 값을 모두 걷어낸다. 살아 있는 값이 있으면 하나를 꺼내 counts와 실제 큐 크기 size를 줄인다. 최종 최솟값·최댓값을 읽기 전에도 양쪽 top을 정리해야 결과에 오래된 복사본이 섞이지 않는다.

상대 힙에서 삭제한 값을 즉시 찾으면 연산이 느려진다

삭제할 때마다 반대쪽 힙에서 같은 값을 list.remove()로 찾아 지우고 heapify()하면 동기화는 되지만, 한 번의 연산이 선형 시간까지 늘어난다. 연산이 최대 1,000,000개이므로 두 힙의 복사본은 counts로 느슨하게 연결하고 stale 값은 top에서만 정리해야 로그 시간 특성을 유지할 수 있다.

전체 연산 수에 따른 복잡도

삽입은 두 힙에 원소를 넣으므로 O(log m)이다. 한 번의 삭제가 stale 원소를 여러 개 걷어낼 수 있어 그 삭제만 보면 O(m)까지 걸릴 수 있지만, 각 원소는 각 힙에서 한 번만 삽입되고 한 번만 제거된다. 따라서 모든 지연 삭제를 합쳐 계산한 전체 시간 복잡도는 O(m log m)이며, m은 명령 수다.

두 힙과 개수 사전에 저장되는 원소 수가 연산 수에 비례하므로 공간 복잡도는 O(m)다.

3. 문제 해결 코드 (Python)

import heapq


def solution(operations):
    min_heap = []
    max_heap = []
    counts = {}
    size = 0

    def clean_min():
        while min_heap and counts.get(min_heap[0], 0) == 0:
            heapq.heappop(min_heap)

    def clean_max():
        while max_heap and counts.get(-max_heap[0], 0) == 0:
            heapq.heappop(max_heap)

    for operation in operations:
        command, value_text = operation.split()
        value = int(value_text)

        if command == "I":
            heapq.heappush(min_heap, value)
            heapq.heappush(max_heap, -value)
            counts[value] = counts.get(value, 0) + 1
            size += 1
            continue

        if size == 0:
            continue

        if value == 1:
            clean_max()
            if max_heap:
                removed = -heapq.heappop(max_heap)
                counts[removed] -= 1
                size -= 1
        else:
            clean_min()
            if min_heap:
                removed = heapq.heappop(min_heap)
                counts[removed] -= 1
                size -= 1

    if size == 0:
        return [0, 0]

    clean_min()
    clean_max()
    return [-max_heap[0], min_heap[0]]

size는 실제 큐에 살아 있는 원소 수이므로 빈 큐에서의 삭제를 빠르게 건너뛸 수 있다. max_heap에는 -value가 저장되므로 최상단을 꺼낸 뒤 다시 부호를 바꾸면 실제 최댓값이 된다. counts의 항목을 바로 사전에서 지우지 않고 0으로 두어도 지연 삭제 판정에는 문제가 없다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 양쪽 삭제, 빈 큐, 중복 값을 확인할 수 있다.

assert solution(["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]) == [0, 0]
assert solution(["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]) == [333, -45]
assert solution(["I 5", "I 5", "I 3", "D 1"]) == [5, 3]

4. 공식 예제와 추가 검증

공식 예제 1

입력: ["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]
기대 출력: [0, 0]
확인 결과: 통과

공식 예제 2

입력: ["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]
기대 출력: [333, -45]
확인 결과: 통과

추가 검증 1: 빈 큐에서 삭제

입력: ["D 1", "D -1", "I 4", "D 1"]
기대 출력: [0, 0]
확인 결과: 통과
검증 목적: 빈 큐의 삭제를 무시하고 이후 삽입과 삭제를 처리하는지 확인

추가 검증 2: 중복 값

입력: ["I 5", "I 5", "I 3", "D 1"]
기대 출력: [5, 3]
확인 결과: 통과
검증 목적: 같은 값 두 개 중 하나만 삭제하고 남은 중복 값을 유지하는지 확인

추가 검증 3: 삽입과 같은 값의 삭제

입력: ["I 7", "D 1", "I 7", "D -1"]
기대 출력: [0, 0]
확인 결과: 통과
검증 목적: 같은 값이 최대·최소 삭제 방향에서 모두 정상적으로 제거되는지 확인

5. 다른 풀이 방식 검색 및 비교

참고 글도 최소 힙과 음수로 표현한 최대 힙을 함께 사용하는 방향을 설명한다. 이 글의 구현은 두 힙을 사용한다는 점은 같지만, 한쪽 힙에서 삭제한 원소를 counts로 표시하고 반대쪽에서는 최상단에 도달했을 때만 버리는 지연 삭제를 사용한다. 따라서 중간 원소를 remove()로 찾거나 매번 heapify()하지 않는다.

마무리

두 힙에 같은 원소를 저장하는 방식에서는 자료구조를 즉시 완전히 동기화하려고 하기보다, 현재 결과에 필요한 최상단만 유효성 검사하는 것이 핵심이다. 최소 힙, 최대 힙, 개수 사전을 결합하면 중복 값과 빈 삭제를 처리하면서도 많은 연산을 로그 시간으로 처리할 수 있다.

#힙#프로그래머스#난이도 3