Baekjoon 7662. 이중 우선순위 큐 / Python

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

문제 설명

연산들을 수행하고 최종적으로 큐에 남아있는 데이터 중 최대, 최솟값을 출력한다.

비어있다면 EMPTY를 출력한다.

코드 설명

최대 힙, 최소 힙을 모두 사용한다.

find 배열을 사용해 해당 인덱스의 숫자의 유효성을 체크한다.

시간복잡도

삽입 : O(log n) (최악)

삭제 : O(log n) (최악)

전체 : O(n log n)

import sys
input = sys.stdin.readline
from heapq import heappop, heappush

# 테스트 케이스 수 입력
T = int(input())

for _ in range(T):
    # 연산의 개수 입력
    n = int(input())
    
    # 최대 힙과 최소 힙
    q1 = []
    q2 = []
    
    # 해당 인덱스의 숫자가 유효한지 체크하는 리스트
    find = [1] * n
    
    for idx in range(n):
        # 명령어와 숫자 입력
        command, num = input().split()
        num = int(num)
        
        if command == 'I':
            # 숫자를 최대 힙과 최소 힙에 삽입
            heappush(q1, (-num, idx))
            heappush(q2, (num, idx))
        else:
            # 최댓값 삭제
            if num == 1 and q1:
                find[heappop(q1)[1]] = 0
            # 최솟값 삭제
            if num == -1 and q2:
                find[heappop(q2)[1]] = 0
        
        # 최대 힙의 유효하지 않은 값 제거
        while q1 and not find[q1[0][1]]:
            heappop(q1)
        
        # 최소 힙의 유효하지 않은 값 제거
        while q2 and not find[q2[0][1]]:
            heappop(q2)

    # 결과 출력
    if q1:
        print(-q1[0][0], q2[0][0])
    else:
        print('EMPTY')