사용 언어: python 3.9.1

❓ Problem

백준 7662. 이중 우선순위 큐

📕 피드백

1. 발전 방향

문제를 읽으면서 반례가 될 만한 부분들을 차근차근 기록해 나가야 할 것 같음.

2. 느낀점

메모리 초과 때문에 어떤 변수에 미리 한꺼번에 저장해두고 쭉 진행하는 것보다는, for문을 진행하면서 input을 따로 분산해서 받는 게 더 나을 듯.

🚩 Solution

1. 접근법

TRY 1

식별자로 안했고, info를 dict형으로 : key=큐의정수, val=0 if (삭제된 적 있는 경우) else 1 으로 구현했는데, 같은 정수가 다른 데이터로 삽입/삭제되는 경우가 있음을 본문에서 명시했었다..

TRY 2

그래서 반례를 적용해서 info를 리스트로 하되, 길이를 k개로 둬서 최대한 메모리에 낭비가 없도록 했다. 이때 info에서 key=식별자, 즉 정수가 같아도 서로 다른 명령어로 들어왔으면(I 32, I 32) 서로 식별할 수 있는 식별자로 info에 삽입할 수 있게 했다. 이때 식별자는 '지금까지 수행한 명령어 개수'로 for문의 i로 설정했다.

TRY 3

그렇게 반례를 해결해도 계속 메모리 초과가 나서

1. 우선 삭제 명령이 들어왔을때 x = heapq.heappop()으로 매번 pop되는 값들을 저장해 뒀었는데 그걸 그냥 heaqp.heappop()으로 버리는 걸로 처리

   : 10%? 정도까지 진행하다가 메모리 초과 뜸

2. 그래도 계속 메모리 초과가 떠서 commands = list(map()) 이렇게 I나 D에 관련한 명령들을 한꺼번에 받았던 걸 → c = readline().split()으로 for문에 나눠서 받았다.

   : 메모리 초과 해결!

2. 코드

import sys, heapq

T = int(sys.stdin.readline()); ans = []
for _ in range(T):
    k = int(sys.stdin.readline())
    maxq = []; minq = []; info = [False]*k

    for i in range(k):
        # 명령마다 처리
        c = sys.stdin.readline()[:-1].split()
        if c[0] == 'I':
            # * INSERT
            heapq.heappush(maxq, (-1 * int(c[1]), i))
            heapq.heappush(minq, (int(c[1]), i))
            info[i] = True
        else:
            # * POP
            if int(c[1]) == 1 and len(maxq) != 0:
                # 최댓값 삭제
                while(maxq and not info[maxq[0][1]]):
                    heapq.heappop(maxq)
                if maxq: info[maxq[0][1]] = False; heapq.heappop(maxq)
            elif int(c[1]) == -1 and len(minq) != 0:
                # 최솟값 삭제
                while(minq and not info[minq[0][1]]):
                    heapq.heappop(minq)
                if minq: info[minq[0][1]] = False; heapq.heappop(minq)

    # 마지막 max_val, min_val
    while(minq and not info[minq[0][1]]): heapq.heappop(minq)
    while(maxq and not info[maxq[0][1]]): heapq.heappop(maxq)
    
    ans.append('%d %d'%(-1*maxq[0][0], minq[0][0]) if maxq and minq else "EMPTY")
    
for a in ans:
    print(a)

3. 결과

시간 복잡도 분석

O(b*loga), b=삽입명령개수, a=삭제명령개수