import heapq

def solution(operations):
    answer = []
    min_q = []
    max_q = []
    s_q = {}
    for i in operations :
        op, num = i.split(" ")
        if op == "I" :
            heapq.heappush(min_q, int(num))
            heapq.heappush(max_q, -int(num))
        else :
            while min_q and max_q :
                temp = 0
                if num == "-1" :
                    temp = heapq.heappop(min_q)
                else :
                    temp = -heapq.heappop(max_q)
                if temp in s_q :
                    del s_q[temp]
                    continue
                else :
                    s_q[temp] = 1
                    break
    min_n, max_n = 0,0
    while min_q :
        temp = heapq.heappop(min_q)
        if temp not in s_q : 
            min_n = temp
            break
    while max_q :
        temp = -heapq.heappop(max_q)
        if temp not in s_q : 
            max_n = temp
            break
    return [max_n,min_n]

• 문제정리

  이중 우선순위 큐는 삽입, 최댓값 삭제, 최솟값 삭제가 가능한 자료구조를 말합니다.

  여러 명령이 주어질때 명령실행 후 큐에 남아있는 값의 [최댓값, 최솟값]을 반환하는 문제

• 풀이과정

  일단 큐에서 max나 min을 사용하여 값을 찾은다음 값을 큐에서 뺄 경우 시간복잡도로 인하여 시간초과가 날것으로 생각되었고 min힙과 max힙을 두개사용하여 풀이하고자 하였다.

  문제는 최댓값을 삭제했을때 최솟값을 삭제했을때 두개의 힙을 값들을 서로 동기화 해줘야한다는 문제였다.

  dict를 이용해서 삭제시 값을 dict에 넣고 다음 삭제 때 dict을 사용하여 이미 삭제된값인지 확인하였다.

  이미 삭제된값일경우 다음 값을 찾는 방식으로 풀이하였다.

• 풀이 후

  dict를 확인하며 계속 힙에서 뺴줘야함으로 조건과 반복문이 많아져 코드가 깔끔하지 않은 것 같다는 생각이들었다.

  다른 사람의 풀이를 보면서 개선하고 싶었는데 테스트케이스가 시간복잡도를 보는 테스트가 없어 heaqp를 사용하지 않아도 통과되서 그런지 max, min으로 풀이한 사람들이 많았다.

  동기화를 안해도 테스트케이스가 통과되는 문제도 있었다.

  여러 사람들이 안되는 반례를 올려놨는데 해당 반례 테스트케이스를 넣으니 통과되는 것을 보니 문제 없이 풀이한것 같아 다행이라는 생각이 들었다.