[백준/Python] 🥇 7662번 이중 우선순위 큐

문제

 

이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다.

정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자.

Q에 적용될 일련의 연산이 주어질 때 이를 처리한 후 최종적으로 Q에 저장된 데이터 중 최댓값과 최솟값을 출력하는 프로그램을 작성하라.

입력

입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적용할 연산의 개수를 나타내는 정수 k (k ≤ 1,000,000)가 주어진다. 이어지는 k 줄 각각엔 연산을 나타내는 문자(‘D’ 또는 ‘I’)와 정수 n이 주어진다. ‘I n’은 정수 n을 Q에 삽입하는 연산을 의미한다. 동일한 정수가 삽입될 수 있음을 참고하기 바란다. ‘D 1’는 Q에서 최댓값을 삭제하는 연산을 의미하며, ‘D -1’는 Q 에서 최솟값을 삭제하는 연산을 의미한다. 최댓값(최솟값)을 삭제하는 연산에서 최댓값(최솟값)이 둘 이상인 경우, 하나만 삭제됨을 유념하기 바란다.

만약 Q가 비어있는데 적용할 연산이 ‘D’라면 이 연산은 무시해도 좋다. Q에 저장될 모든 정수는 -231 이상 231 미만인 정수이다.

출력

출력은 표준출력을 사용한다. 각 테스트 데이터에 대해, 모든 연산을 처리한 후 Q에 남아 있는 값 중 최댓값과 최솟값을 출력하라. 두 값은 한 줄에 출력하되 하나의 공백으로 구분하라. 만약 Q가 비어있다면 ‘EMPTY’를 출력하라.

 

예제 입력 1 

 

 

 

 

풀이

 

첫 번째 도전

 

반대 큐에서 삭제되는 값을 min_heap.pop(-1)처럼 단순히 배열 끝 값을 없애주면 힙 속성이 유지되지 않는다.

나는 어차피 완전 이진 트리이고, 트리에서 가장 마지막 값일텐데 상관없겠다고 생각해버렸다.

그치만 오답이었죠? 땡 !

import heapq

min_heap = []
max_heap = []

TC = int(input())
for tc in range(TC):
    commands = int(input())
    for c in range(commands):
        oper, num = input().split()
        num = int(num)
        if oper == 'I':
            heapq.heappush(min_heap, num)
            heapq.heappush(max_heap, -num)
        else:
            if len(min_heap) == 0 and len(max_heap) == 0:
                continue
            if num < 0: # 우선순위 낮은 숫자 제거
                heapq.heappop(min_heap)
                max_heap.pop(-1)
            else: # 우선순위 높은 숫자 제거
                -heapq.heappop(max_heap)
                min_heap.pop(-1)
    if len(min_heap) == 0:
        print("EMPTY")
    else:
        print(-max_heap[0], min_heap[0])

 

 

📌 우선순위 큐에서 '지연 삭제(Lazy Deletion)'

삭제 요청이 들어왔을 때 실제 큐에서 즉시 제거하지 않고, 삭제되었다는 표시(플래그)만 해두었다가 해당 원소가 추출될 때(pop) 유효한지 확인하고 실제로 제거하는 방식입니다. 이는 중간 원소 삭제가 어려운 힙(Heap) 자료구조의 특성상, 이중 우선순위 큐처럼 최댓값과 최솟값을 동시에 관리해야 하는 문제에서 효율적으로 적용되며, 힙에 쌓인 유효하지 않은 원소들을 while 루프 등으로 건너뛰어 실제 데이터만 추출하는 방식으로 구현됩니다. 

📌 동일한 정수가 삽입될 수 있다

힙에 삽입할 때 heapq.heappush(min_heap, (num, idx))와 같이 몇 번째 명령어인지 인덱스 정보를 넣어 관리한다.

삽입 시, 같은 값이 부호만 다른채 두 힙에 동시에 들어감
heapq.heappush(min_heap, (num, idx))
heapq.heappush(max_heap, (-num, idx))

❗ 문제 상황
I 5
I 3
min_heap = [(3, 2), (5, 1)]
max_heap = [(-5, 1), (-3, 2)]

D -1 # 최소값 삭제 → min_heap에서 3 삭제
min_heap = [(5, 1)] # (3, 2) 제거됨
max_heap = [(-5, 1), (-3, 2)] # 아직 (-3, 2) 남아있음

👉 max_heap에서 해당 값을 일일이 삭제 & 힙 구조 유지하기 어렵기 때문에,
      visited.add(2)으로 “2는 이미 삭제된 원소다” 라고 표시만 해두고 나중에 결과 출력할 때 참고함(lazy deletion)
      num은 부호만 다르고 같은 값을 가지기 때문에, idx 값으로 visited를 체크하는 것이 포인트 !
      ex) visited.add(2) = "숫자 2는 삭제된 원소다" (X) "2번째 명령어로 들어온 숫자 3은 삭제된 원소다" (O)

 

 

 

최종 코드

 

📌 top 정합성 보장

출력 전에 while문으로 각 min_heap과 max_heap에 대해 최종 정리를 해주어야 한다.

힙의 맨 위 원소가 visited에 있으면 이미 삭제된 가짜 데이터이기 때문에 버려야 하기 때문.
힙의 원소를 사용할 때 무조건 삭제되었는지 체크를 해야 하는 것이다.

❗ 문제 상황
1
4
I 5
I 3
D -1
D 1

최종 정리 코드 없으면?
min_heap = [(5, 1)]
max_heap = [(-3, 2)]
visited = (2, 1) # 2번째 명령어인 숫자 3과, 1번째 명령어인 숫자5는 삭제된 데이터다
출력: 3 5 ❌ # 정답: EMPTY, min_heap과 max_heap에 남아있는 인덱스 값이 모두 삭제된 데이터의 인덱스임.

import heapq

TC = int(input())
for tc in range(TC):
    commands = int(input())
    idx = 0
    visited = set() # 혹은 visited = [False] * tc
    min_heap = []
    max_heap = []
    for c in range(commands):
        oper, num = input().split()
        num = int(num)
        idx += 1
        if oper == 'I':
            heapq.heappush(min_heap, (num, idx))
            heapq.heappush(max_heap, (-num, idx))
        else:
            if not min_heap and not max_heap:
                continue
            if num < 0: 
                # ☆index기반 lazy deletion: 이미 삭제된 원소들 제거
                while min_heap and min_heap[0][1] in visited:
                    heapq.heappop(min_heap)
                # 우선순위 낮은 숫자 제거
                if min_heap:
                    del_num, del_idx = heapq.heappop(min_heap)
                    visited.add(del_idx)
            else:
                # ☆index기반 lazy deletion: 이미 삭제된 원소들 제거
                while max_heap and max_heap[0][1] in visited:
                    heapq.heappop(max_heap)
                # 우선순위 높은 숫자 제거
                if max_heap:
                    del_num, del_idx = heapq.heappop(max_heap)
                    visited.add(del_idx)
    # 최종 정리
    # 힙의 top이 이미 다른 힙에서 삭제된 원소일 수 있음
    while min_heap and min_heap[0][1] in visited:
        heapq.heappop(min_heap)
    
    while max_heap and max_heap[0][1] in visited:
        heapq.heappop(max_heap)
                
    if not min_heap:
        print("EMPTY")
    else:
        print(-max_heap[0][0], min_heap[0][0])

 

 

 

느낀점

 

Heap 자료구조 특성 상, 트리 구조로 되어 있어 노드를 삭제하게 되면 정합성 문제가 발생하는데

이를 쉽게 해결하기 위한 lazy deletion이라는 방식을 처음 알게 되었다 !

 

 

삭제된 원소를 인덱스(명령어 순서) 값으로 관리하고 (num 값이 유일하다면 num으로 관리해도 무방)

원소에 접근할 때마다 삭제된 값인지 확인하는 절차를 거치는 것. 

 

 

위 문제에서는 데이터를 지울 때, 이미 지워진 데이터는 건너뛰고 지워지지 않은 top의 원소를 삭제했고

마지막에 결과를 출력할 때, 각 heap에 남은 원소를 정리해 정합성을 유지시켜주는 용도로 사용되었다.

 

 

Heap 특성에 대해 한 발 더 이해하게 됨 ! 너 이런 성격을 가진 친구였구낭 ?

다음에 더 야무지게 써먹어줄게ㅎ_ㅎ ~

 

 

lazy deleteion...... 게으른 삭제.... 대충 표시만 해두고 한 번에 while문으로 체크.......

꼭 방 청소, 화장실 청소 해야되는데 알고만 있으면서 미루다가 엄마한테 혼나니까 시작하는 언니같은 느낌이랄까...