백준 7662 <이주 우선순위 큐> Python

https://www.acmicpc.net/problem/7662

---

우선순위 큐를 두 개 사용해서 풀 수 있는 문제입니다.

최대힙, 최소힙 두 개를 사용해 풀 수 있는데, 문제는 이 두 힙을 동기화 시키는 것 입니다.

 

가장 작은 수를 최소힙을 통해 제거했다고 가정하겠습니다. 최대힙에서는 이 수를 제거한 사실이 자동으로 업데이트 되지 않습니다. 그렇다고 최대힙에서 해당 수를 찾아 제거하는 방식은 우선순위 큐를 사용하는 이점을 살릴 수 없습니다. 그렇기에 우리는 다른 방식을 찾아야 합니다.

 

일반적인 방법으로 쿼리의 순서를 기억해 삭제했는지 체크하는 방법이 있습니다.

그래프를 탐색할 때 탐색여부를 체크하기 위해 visited 를 만드는 것 처럼 삭제한 쿼리를 기억해 최대힙 / 최소힙 에서 해당 데이터를 삭제 시 이미 삭제된 쿼리의 경우 다시 작동시켜 중복을 피할 수 있습니다.

 

그렇다면 굳이 쿼리의 순서를 기억하는 것이 아닌 수 자체를 기억하면 되지 않는가 한다면 중복되는 수가 존재할 시 문제가 되기 때문에 중복이 되지 않는 것이 명확한 쿼리의 순서로 체크하면 되겠습니다.

 

삽입 / 삭제 의 작업이 끝났다면 두 힙을 마지막으로 병합해주어야 합니다.

말은 병합이지만 하나의 힙을 정해 삭제되지 않고 남아있는 수를 모아주는 작업입니다.

이 중 최대 / 최솟값을 찾으면 되겠습니다.

---

import sys
import heapq
from bisect import insort

input = sys.stdin.readline


def solution(k, querys):
    # 최대 / 최소 힙
    max_heap = []
    min_heap = []
    # 동기화를 위한 삭제 체크
    deleted = [False for _ in range(k)]
    # 쿼리 순회
    for q in range(k):
        # 쿼리
        query = querys[q]
        # 삽입
        if query[0] == 'I':
            # 큐에 삽입
            heapq.heappush(min_heap, [int(query[1]), q])
            heapq.heappush(max_heap, [-int(query[1]), q])
        
        # 삭제
        else:
            # 최소
            if query[1] == '1':
                # 반복
                while max_heap:
                    # 삭제된 수, 쿼리 인덱스
                    deleted_num, query_idx = heapq.heappop(max_heap)
                    # 이미 삭제된 인덱스면
                    if deleted[query_idx]:
                        # 다시
                        continue
                    
                    # 삭제되지 않은 인덱스면
                    else:
                        # 삭제 기록
                        deleted[query_idx] = True
                        # 끝
                        break
            
            # 최대
            else:
                # 반복
                while min_heap:
                    # 삭제된 수, 쿼리 인덱스
                    deleted_num, query_idx = heapq.heappop(min_heap)
                    # 이미 삭제된 인덱스면
                    if deleted[query_idx]:
                        # 다시
                        continue
                    
                    # 삭제되지 않은 인덱스면
                    else:
                        # 삭제 기록
                        deleted[query_idx] = True
                        # 끝
                        break

    # 큐 병합
    queue = []
    for num, idx in max_heap:
        # 삭제되지 않은 수만 큐에 삽입
        if not deleted[idx]:
            queue.append(-num)
    
    if not queue:
        print('EMPTY')
    
    else:
        print(f'{max(queue)} {min(queue)}')


# 입력
T = int(input().strip())
for _ in range(T):
    k = int(input().strip())
    querys = [list(input().strip().split()) for _ in range(k)]
    
    solution(k, querys)