[baekjoon] 백준 7662번 : 이중 우선순위 큐 (by python 파이썬) 이중 힙큐

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

7662번: 이중 우선순위 큐

 

정답 code

#이중 우선순위 큐
import heapq
import sys
input = sys.stdin.readline

t = int(input())


for _ in range(t):
    k = int(input())
    q_max, q_min = [], []
    visited = [False]*k

    for i in range(k):
        s, n = input().split()

        if s == 'I':
            heapq.heappush(q_max, (-int(n), i)) #최대 힙 (-를 붙여 제일 큰수를 최소로 만듬)
            heapq.heappush(q_min, (int(n), i)) #최소 힙
            visited[i] = True #정수 생성

        elif s == 'D':
            if n == '1':
                #만약 정수가 없다면(=False) 힙 제거
                while q_max and visited[q_max[0][1]] == False:
                    heapq.heappop(q_max)
                #최대힙 존재시 제거
                if q_max:
                    visited[q_max[0][1]] = False
                    heapq.heappop(q_max)

            else:
                #만약 정수가 없다면(=False) 힙 제거
                while q_min and visited[q_min[0][1]] == False:
                    heapq.heappop(q_min)
                #최소 힙 존재시 제거
                if q_min:
                    visited[q_min[0][1]] = False
                    heapq.heappop(q_min)

    if True not in visited: #정수 없으면 empty출력
        print("EMPTY")
    
    else: #정수가 없다면
        #존재하지 않는 정수(=False)제거
        while q_max and visited[q_max[0][1]] == False:
            heapq.heappop(q_max)
        while q_min and visited[q_min[0][1]] == False:
            heapq.heappop(q_min)
        #최대값(-붙여뒀음으로 다시 -로 +만들기), 최소값 출력
        print(-q_max[0][0], q_min[0][0])

 

solution

처음엔 하나의 힙큐로 문제를 풀어나갔는데 해결하지 못하는 부분이 있었다.

결국 힙큐 두개를 선언해서 풀어야 했는데 두 힙큐를 동기화하기위해 visited를 이용해 동기화 시켜 해결하면된다.

 

I로 입력이 들어오면 q_max  와 q_min에 각각 추가하고 visited[i]도 True 로 바꿔준다.

 

D로 입력이 들어오면 1인경우와 -1인경우를 나눠서 만약 q_max나 q_min에 존재해도 visited가 False로 되어있다면

다른 힙큐에서 삭제 되었음으로 해당 힙큐에서도 지우고 최대값이나 최솟값을 빼내면 된다.

 

모든 과정이 끝나고도 q_max와 q_min을 동기화 시켜주고 최대값과 최솟값을 출력하면 된다.