백준 7662 - 이중 우선순위 큐(Python3)

코드

시간 초과

import heapq
T = int(input())

for _ in range(T):
    k = int(input())
    heap_min = []
    heap_max = []
    
    for _ in range(k):
        cmd = input().split()
        rule = cmd[0]
        n = int(cmd[1])
        
        if rule == 'I':
            heapq.heappush(heap_min, n)
            heapq.heappush(heap_max, -n)
            
        if rule == 'D':
            if not heap_min or not heap_max:
                continue
            
            if n == -1:
                heapq.heappop(heap_min)
            else:
                heapq.heappop(heap_max)

# 두 힙이 공통으로 값을 가진 애들만 최종 리스트로 반환
result = [x for x in heap_min if -x in heap_max]                

print(result)

if not heap_min or not heap_max:
    print('EMPTY')
else:
    print(max(result), min(result))
    

구글링 참고

import heapq, sys

T = int(sys.stdin.readline())

for _ in range(T):
    
    # 연산의 개수 k의 최댓값 1000000
    k = int(sys.stdin.readline())
    
    # 최소힙 최대힙
    heap_min = []
    heap_max = []
    
    # k의 개수 만큼 visited 리스트 생성
    # 역할 : 연산에 부여된 숫자를 인덱스로 사용하여
    #        해당 연산이 수행됐으면 두 큐에 동시 적용하기 위한 구분
    visited = [False] * 1000001
    
    # i를 식별자로 사용 => visited 리스트의 인덱스와 일치
    # I 연산이 두 힙에 모두 적용됐는가를 확인하는 용도
    for i in range(k):
        cmd = sys.stdin.readline().rstrip().split()
        rule = cmd[0]
        n = int(cmd[1])
        
        if rule == 'I':
            heapq.heappush(heap_min, (n, i))
            heapq.heappush(heap_max, (-n, i))
            visited[i] = True
        
        else:
            if n == 1:
                while heap_max and not visited[heap_max[0][1]]:
                    heapq.heappop(heap_max)

                if heap_max:
                    visited[heap_max[0][1]] = False
                    heapq.heappop(heap_max)
            else:
                while heap_min and not visited[heap_min[0][1]]:
                    heapq.heappop(heap_min)

                if heap_min:
                    visited[heap_min[0][1]] = False
                    heapq.heappop(heap_min)
                    
    while heap_min and not visited[heap_min[0][1]]:
        heapq.heappop(heap_min)
        
    while heap_max and not visited[heap_max[0][1]]:
        heapq.heappop(heap_max)
        
    if heap_min and heap_max:
        print(-(heap_max[0][0]), heap_min[0][0])
    else:
        print('EMPTY')
    

문제 해설

시간 초과로 혼쭐난 문제…

처음 푼 풀이가 시간 초과로 틀렸지만 사실 반례가 없는 지도 잘 모르겠다 ㅠㅠ 다양한 방법으로 시간 복잡도를 줄여보려고 노력했으나 핵심 로직을 건들이지 않는 이상 시간 복잡도를 획기적이게 줄일 수 있는 방법이 떠오르지 않아 다른 분들은 어떤 식으로 풀이를 하셨나 참고하여 문제를 풀었다.

시간이 좀 지나고 다시 한 번 풀어봐야겠다…(2022-03-14)

참고 블로그