[자료구조/힙] 백준 7662 이중 우선순위 큐 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

7662번: 이중 우선순위 큐

 

 

 

2. 문제 풀이

 최댓값과 최솟값을 둘 다 반환할 수 있는 우선순위 큐를 설계하는 문제입니다.

 

2022.02.20 - [Algorithm] - [Algorithm] 힙(heap), 최소/최대로 정렬하는 우선순위 큐

[Algorithm] 힙(heap), 최소/최대로 정렬하는 우선순위 큐

 파이썬의 heapq 라이브러리를 이용해서 우선순위 큐를 구현합니다.

 

2022.02.20 - [Algorithm] - [자료구조/힙] 백준 1927 최소 힙 - Python

2022.02.20 - [Algorithm] - [자료구조/힙] 백준 11279 최대 힙 - Python

 최솟값과 최댓값을 반환받기 위해서는 최소 힙과 최대 힙을 함께 사용해야 합니다. 두 가지 종류의 힙 구현 방법 및 설명은 위 링크에서 보실 수 있습니다.

 

 

 

3. 코드

T = int(input())
for _ in range(T):
    k = int(input()) #연산횟수
    maxHeap = [] #최대 힙
    minHeap = [] #최소 힙
    check = [False]*k #체크(최대 k번 push)

 최대 힙과 최소 힙을 모두 구현합니다. 숫자를 추가할 때는 둘 다 push해주면 되지만, 최소/최대값을 반환할 때는 둘 다 pop해줄 수가 없습니다. 따라서 check에 pop한 원소를 표시하고, 이미 pop한 원소일 경우에 제외시킵니다.

 

 

for idx in range(k):
    op, n = input().rstrip().split()
    n = int(n)

    if op == "I": #push
        heapq.heappush(maxHeap, (-n, idx)) #최대 힙 push
        heapq.heappush(minHeap, (n, idx)) #최소 힙 push
        check[idx] = True

 (숫자, 인덱스) 튜플로 힙에 push합니다. 인덱스는 for문의 반복횟수입니다.

 

 

elif n == -1: #최솟값 삭제
    #check한 원소가 True일 때까지 삭제
    while minHeap and not check[minHeap[0][1]]:
        heapq.heappop(minHeap)

    # 체크에 뺄 원소 False로 바꾸고 pop
    if minHeap:
        check[minHeap[0][1]] = False
        heapq.heappop(minHeap)

 최솟값 pop하기 전에, 이미 최대 힙에서 빠진 숫자인지 체크합니다.

 최솟값을 pop한 후에는 뺀 숫자의 인덱스를 False로 바꿉니다.

 

 

else: #최댓값 삭제
    # check한 원소가 True일 때까지 삭제
    while maxHeap and not check[maxHeap[0][1]]:
        heapq.heappop(maxHeap)

    # 체크에 뺄 원소 False로 바꾸고 pop
    if maxHeap:
        check[maxHeap[0][1]] = False
        heapq.heappop(maxHeap)

 최댓값도 마찬가지로 check가 True일 때까지 삭제하고, 최댓값을 pop하고 표시합니다.

 

 

# 마지막으로 check
while minHeap and not check[minHeap[0][1]]:
    heapq.heappop(minHeap)
while maxHeap and not check[maxHeap[0][1]]:
    heapq.heappop(maxHeap)

 연산이 끝나면, 마지막으로 빠진 숫자가 없는지 확인합니다.

 

 

if not maxHeap or not minHeap: #비어있을 경우
    print("EMPTY")
else: #최댓값, 최솟값 출력
    print(-maxHeap[0][0], minHeap[0][0])

 비어있을 경우 EMPTY를 출력하고, 아닐 경우 최댓값과 최솟값을 출력합니다.

 (heap에 숫자가 1개만 남았을 경우에는 그 값이 최댓값이자 최솟값입니다.)

 

 

<전체 코드>

import sys
import heapq
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    k = int(input()) #연산횟수
    maxHeap = [] #최대 힙
    minHeap = [] #최소 힙
    check = [False]*k #체크(최대 k번 push)
    for idx in range(k):
        op, n = input().rstrip().split()
        n = int(n)

        if op == "I": #push
            heapq.heappush(maxHeap, (-n, idx)) #최대 힙 push
            heapq.heappush(minHeap, (n, idx)) #최소 힙 push
            check[idx] = True

        elif not maxHeap or not minHeap: #비어있다면 무시
            pass

        elif n == -1: #최솟값 삭제
            #check한 원소가 True일 때까지 삭제
            while minHeap and not check[minHeap[0][1]]:
                heapq.heappop(minHeap)

            # 체크에 뺄 원소 False로 바꾸고 pop
            if minHeap:
                check[minHeap[0][1]] = False
                heapq.heappop(minHeap)

        else: #최댓값 삭제
            # check한 원소가 True일 때까지 삭제
            while maxHeap and not check[maxHeap[0][1]]:
                heapq.heappop(maxHeap)

            # 체크에 뺄 원소 False로 바꾸고 pop
            if maxHeap:
                check[maxHeap[0][1]] = False
                heapq.heappop(maxHeap)

    # 마지막으로 check
    while minHeap and not check[minHeap[0][1]]:
        heapq.heappop(minHeap)
    while maxHeap and not check[maxHeap[0][1]]:
        heapq.heappop(maxHeap)

    if not maxHeap or not minHeap: #비어있을 경우
        print("EMPTY")
    else: #최댓값, 최솟값 출력
        print(-maxHeap[0][0], minHeap[0][0])