BOJ 7662 이중 우선순위 큐

https://www.acmicpc.net/problem/7662
시간 6초, 메모리 256MB
input :

• T 테스트 데이터
• k (1 <= k <= 1,000,000)
• l n

output :

• 최댓값과 최솟값을 출력
• 만약 Q가 비어있다면 ‘EMPTY’를 출력

조건 :

• 동일한 정수가 삽입될 수 있음
• ‘D 1’는 Q에서 최댓값을 삭제하는 연산
• ‘D -1’는 Q 에서 최솟값을 삭제하는 연산
• 최댓값(최솟값)을 삭제하는 연산에서 최댓값(최솟값)이 둘 이상인 경우, 하나만 삭제
• Q가 비어있는데 적용할 연산이 ‘D’라면 이 연산은 무시

---

기말고사 시험의 베이스가 되었던 문제이다.

일단 우선적으로 리스트 2개를 이용해서 max, min 리스트를 만들어 두고 이 값을 업데이트 하는 방향으로 문제를 풀어 나갔다.
값들을 삭제하는 경우에 이미 삭제가 되었는데 다른 리스트에는 남아있는 경우가 발생할 수 있다.
이를 해결 하기위해 cnt 라는 변수를 통해 개수를 저장하고 있게 한다면 어떨까 싶어 이를 이용했다.

그러나 이 경우 중복된 수를 확인 할 수 없다.
그래서 딕셔너리?를 이용해서 풀어볼까 했지만 계속 틀렸습니다.를 받았다.

다른 풀이들을 살펴 보니 위의 방법들도 필요하지만 가장 중요한 것은 리스트 안에서 값을 찾을 때 현재 값이 이미 삭제 되어 있는 값인데도 남아있는 경우를 유의 해야 하는 것이다.
그를 위해 while 문의 조건이 생기게 되고 리스트의 0번째 원소를 꺼내서 확인을 해야 한다.

data 배열이 1백만 까지 있는것은 값이 1백만번 까지 들어올 수 있기 때문이고 idx는 각 원소가 언제 들어왔는 지를 나타낸다.
이 배열을 통해 cnt가 없어도 현재 남아있는 원소의 개수를 알 수 있다.

import sys
from heapq import heappop, heappush

t = int(sys.stdin.readline())
for i in range(t):
    max_num = []
    min_num = []
    data = [0] * 1000000
    k = int(sys.stdin.readline())

    for j in range(k):
        l, n = sys.stdin.readline().split()
        n = int(n)

        if l == 'I':
            heappush(max_num, (-n, j))
            heappush(min_num, (n, j))

            data[j] = 1
        else:
            if n == -1:
                while min_num and data[min_num[0][1]] == 0:
                    heappop(min_num)

                if min_num:
                    data[min_num[0][1]] = 0
                    heappop(min_num)
            else:
                while max_num and data[max_num[0][1]] == 0:
                    heappop(max_num)

                if max_num:
                    data[max_num[0][1]] = 0
                    heappop(max_num)

    if sum(data) == 0:
        print("EMPTY")
    else:
        while max_num and data[max_num[0][1]] == 0:
            heappop(max_num)
        ans_max = -max_num[0][0]

        while min_num and data[min_num[0][1]] == 0:
            heappop(min_num)
        ans_min = min_num[0][0]

        print(f"{ans_max} {ans_min}")