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

문제

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

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

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

나의 풀이(오답1)

import sys
from heapq import heappush,heappop

T=int(input())
for _ in range(T):
    N=int(sys.stdin.readline().strip())
    Max_Heap=[]
    Min_Heap=[]
    length=0
    for _ in range(N):
        command=sys.stdin.readline().strip().split()
        if command[0]=='I':
            heappush(Min_Heap,int(command[1]))
            heappush(Max_Heap,-int(command[1]))
            length+=1
        elif command[0]=='D':
            if length>0:
                if command[1]=='1':
                    heappop(Max_Heap)
                else:
                    heappop(Min_Heap)
                if length==1:
                    Max_Heap=[]
                    Min_Heap=[]
                length-=1
    if length==0:
        print('EMPTY')
    else:
        print(-Max_Heap[0],Min_Heap[0])
                

• MinHeap과 MaxHeap을 따로 두어 푸는 것은 생각을 했는데, 계속 정답이 안되서 정답을 참고했다. 아래 반례는 내가 생각하지 못했던 반례이다. 아래 케이스라면 내가 작성한 코드가 정답일 수 없다. MinHeap에서 삭제되었어도, MaxHeap에서 삭제되지 않아, 다시 한번 삭제되는 경우가 생기기 때문이다. 따라서 아래와 같이 코드를 수정했다.

('I', 10) | max: [-10], min: [10], valid: {10: 1}
('I', 20) | max: [-20, -10], min: [10, 20], valid: {10: 1, 20: 1}
('D', '1') | max: [-10], min: [10, 20], valid: {10: 1, 20: 0}
('I', 30) | max: [-30, -10], min: [10, 20, 30], valid: {10: 1, 20: 0, 30: 1}
('I', 40) | max: [-40, -10, -30], min: [10, 20, 30, 40], valid: {10: 1, 20: 0, 30: 1, 40: 1}
('D', '-1') | max: [-40, -10, -30], min: [20, 40, 30], valid: {10: 0, 20: 0, 30: 1, 40: 1}
('D', '-1') | max: [-40, -10, -30], min: [30, 40], valid: {10: 0, 20: -1, 30: 1, 40: 1}

나의 풀이(오답2)

import sys
from heapq import heappush,heappop

T=int(input())
for _ in range(T):
    N=int(sys.stdin.readline().strip())
    Max_Heap=[]
    Min_Heap=[]
    length=0
    visited=[False]*1000000
    for i in range(N):
        command=sys.stdin.readline().strip().split()
        if command[0]=='I':
            val=int(command[1])
            heappush(Min_Heap,(val,i))
            heappush(Max_Heap,(-val,i))
            visited[i]=True
            length+=1
        elif command[0]=='D':
            if length>0:
                if command[1]=='1':
                    while True:
                        h=heappop(Max_Heap)
                        if visited[h[1]]:
                            visited[h[1]]=False
                            break
                elif command[1]=='-1':
                    while True:
                        h=heappop(Min_Heap)
                        if visited[h[1]]:
                            visited[h[1]]=False
                            break
                if length==1:
                    Max_Heap=[]
                    Min_Heap=[]
                length-=1
    if length==0:
        print('EMPTY')
    else:
        print(-Max_Heap[0][0],Min_Heap[0][0])
                

• 정답을 참고해서, visited라는 리스트를 두고, 이 index의 원소를 지웠는지 안지웠는지 판단할 수 있도록 코드를 짰다. 아무리 생각해봐도 정답인 것 같은데, 계속 20%정도에서 오답이 나와서 정답을 다시 한번 참고했다.

나의 풀이(정답 참고)

import sys
from heapq import heappush,heappop

T=int(input())
for _ in range(T):
    N=int(sys.stdin.readline().strip())
    Max_Heap=[]
    Min_Heap=[]
    length=0
    visited=[False]*1000000
    for i in range(N):
        command=sys.stdin.readline().strip().split()
        if command[0]=='I':
            val=int(command[1])
            heappush(Min_Heap,(val,i))
            heappush(Max_Heap,(-val,i))
            visited[i]=True
            length+=1
        elif command[0]=='D':
            if length>0:
                if command[1]=='1':
                    while True:
                        h=heappop(Max_Heap)
                        if visited[h[1]]:
                            visited[h[1]]=False
                            break
                elif command[1]=='-1':
                    while True:
                        h=heappop(Min_Heap)
                        if visited[h[1]]:
                            visited[h[1]]=False
                            break
                if length==1:
                    Max_Heap=[]
                    Min_Heap=[]
                length-=1
    while Max_Heap and not visited[Max_Heap[0][1]]:
        heappop(Max_Heap)
    while Min_Heap and not visited[Min_Heap[0][1]]:
        heappop(Min_Heap)
    if length==0:
        print('EMPTY')
    else:
        print(-Max_Heap[0][0],Min_Heap[0][0])

• 내가 생각하지 못했던 것은, for문이 끝난 이후에도 visited가 False인데, 남아있는 수가 있을 수 있다는 것이었다. 따라서 while문을 통해서, False인 상태의 수를 모두 제거해주었고 정답을 맞출 수 있었다.