백준 7662 이중 우선순위 큐 파이썬 풀이

난이도 : 골드4

풀이일 : 2402283

https://www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이코드

import sys, heapq

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

for _ in range(T):
    k = int(sys.stdin.readline())
    mini, maxi = [], []
    visited = [False] * 1000001
    for i in range(k):
        A, N = list(sys.stdin.readline().split())
        # 추가 연산 처리
        if A == 'I':
            # visited[i] 사용으로 향후 삭제 연산 대비
            heapq.heappush(mini, [int(N), i])
            heapq.heappush(maxi, [-int(N), i])
            visited[i] = True
        # 최솟값 삭제 연산 처리
        elif A == "D" and int(N) < 0:
            # 삭제 여부 visited 배열로 파악 
            while mini and not visited[mini[0][1]]:
                heapq.heappop(mini)
            if mini:
                # 삭제 요소 visited 처리 및 최소힙에서 제거
                visited[mini[0][1]] = False
                heapq.heappop(mini)
        # 최댓값 삭제 연산 처리
        else:
            while maxi and not visited[maxi[0][1]]:
                heapq.heappop(maxi)
            if maxi:
                # 삭제 요소 visited 처리 및 최대힙에서 제거
                visited[maxi[0][1]] = False
                heapq.heappop(maxi)
    
    # 힙이 존재하며 visited 요소 false인 동안 반복
    while mini and not visited[mini[0][1]]:
        heapq.heappop(mini)
    while maxi and not visited[maxi[0][1]]:
        heapq.heappop(maxi)
    
    if mini and maxi:
        print(-maxi[0][0], mini[0][0])
    else:
        print("EMPTY")

• visited : 최소힙에서의 삭제, 최대힙에서의 삭제 정보를 연동하기 위한 boolean 배열
• mini : 최소힙이므로 일반적인 힙 사용
• maxi : 최대힙으로 사용하기 위해 값 추가 시, -를 붙여 추가
• A가 'I'일 경우, 뒤에 나오는 숫자를 최소힙, 최대힙에 추가
• A가 'D'이며 뒤에 나오는 숫자가 -1일 경우, 최솟값 삭제를 위해, 최소힙에서 이미 삭제된 요소들을 제외한 후 가장 작은 요소 pop
• A가 'D'이며 뒤에 나오는 숫자가 1일 경우, 최댓값 삭제를 위해 최대힙에서 이미 삭제된 요소들을 제외한 후 가장 작은 요소 pop
• 연산이 끝난 후, 최소힙과 최대힙이 존재하면, 삭제된 적이 없는 요소를 맨 처음 요소로 남길때까지 요소 pop
• 최소힙, 최대힙이 있다면 각각의 첫 번재 인자를 출력하며, 없다면 "EMPTY" 출력

---

느낀점

• 여행 중에 풀다가 자꾸 틀려서 중단했던 문제를 이어서 풀어보았다. 입력되는 연산 처리가 끝난 후, while 대신 if라고 조건을 달아서 틀렸던 거였다. 한 이 주 쉬었으니까 다시 꾸준히 풀어야지