이중 우선순위 큐

7662번: 이중 우선순위 큐

 

나의 풀이

import heapq
import sys

def _result_heapq(visit, n_heapq):
    while n_heapq and visit[n_heapq[0][1]]:
        heapq.heappop(n_heapq)
    return n_heapq

def _two_heapq():
    n_ct = int(sys.stdin.readline())
    visit = [False] * n_ct
    min_heapq = []
    max_heapq = []

    for i in range(n_ct):
        n_type, n_num = sys.stdin.readline().rstrip().split()
        if (n_type == 'I'):
            heapq.heappush(min_heapq, (int(n_num), i))
            heapq.heappush(max_heapq, (-int(n_num), i))
        else:
            if (n_num == '1'):
                while max_heapq and visit[max_heapq[0][1]]:
                    heapq.heappop(max_heapq)
                if max_heapq:
                    n_number, n_idx = heapq.heappop(max_heapq)
                    visit[n_idx] = True

            else:
                while min_heapq and visit[min_heapq[0][1]]:
                    heapq.heappop(min_heapq)
                if min_heapq:
                    n_number, n_idx = heapq.heappop(min_heapq)
                    visit[n_idx] = True
    min_heapq, max_heapq = _result_heapq(visit, min_heapq), _result_heapq(visit, max_heapq)
    if min_heapq:
        return f"{max_heapq[0][0] * -1} {min_heapq[0][0]}"
    return "EMPTY"

n = int(sys.stdin.readline())
for _ in range(n):
    print(_two_heapq())

 

 

시간 복잡도

for _ in range(n) : 입력 케이스 숫자 만큼 반복 ( 선형 시간 복잡도 )
    print(_two_heapq()) : 연산을 순회하며 heapq 연산 수행 ( 연산 순회 : 선형 시간 복잡도, 내부 heapq 연산 : 로그 시간 복잡도 )
해당 알고리즘 시간 복잡도 : 이차형 로그 시간 복잡도 ( O( n**2 log n) )