문제풀이/BOJ

[Python] BOJ/백준 7662번 이중 우선순위 큐

서채리 2022. 6. 24. 23:46

[문제]

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

 

7662번: 이중 우선순위 큐

입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적

www.acmicpc.net

 

 

[풀이]

가장 간단한 방법인 max, min 으로 찾는 방법은 시간초과가 나온다 (당연함)

 

파이썬의 우선순위 큐 문제는 heapq, PriorityQueue 두 가지 라이브러리를 사용할 수 있다.

https://stackoverflow.com/questions/36991716/whats-the-difference-between-heapq-and-priorityqueue-in-python?answertab=trending#tab-top

 

What's the difference between heapq and PriorityQueue in python?

In python there's a built-in heapq algorithm that gives you push, pop, nlargest, nsmallest... etc that you can apply to lists. However, there's also the queue.PriorityQueue class that seems to supp...

stackoverflow.com

요약하면 PriorityQueue 는 스레드를 Thread-safe를 위해 확인 절차를 걸쳐 오버헤드가 있고 heapq는 Non-safe 하기 때문에 PriorityQueue 보다 더 빠르다고 한다.

→ 그래서 heapq 라이브러리를 사용하였다.

 

'힙(heap)'이란?

  • 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
  • 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
  • 일종의 반정렬 상태(느슨한 정렬 상태) 유지
    • 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
    • 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리
  • 힙 트리에서는 중복된 값 허용 (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)

이 문제의 중요한 점은 아래 두가지라고 생각한다.

  1. 파이썬의 heapq는 최소힙만 지원하기 때문에 최대힙은 따로 구현해주어야 한다.
    • 최대힙 구현을 위해 삽입 시 입력받은 n 에 -1을 곱하고 결과값을 출력 시에는 -1을 다시 곱한 후 출력
  2. 최대힙, 최소힙을 동기화 시켜주어야 한다.
    • 힙에 push 할 때 입력받은 값 n 과 반복문이 몇 번 수행되었는지 가리키는 변수 i 를 튜플 형태로 함께 넣어줌
      (파이썬의 튜플 비교연산은 첫 번째 원소를 기준으로 판단하기 때문에 힙의 구동에 영향 X)
    • 삭제 연산 시 id를 기준으로 해당 노드가 다른 힙에서 삭제된 노드인지 확인하기 위해 visited 플래그 리스트 사용
      • 이미 삭제된 노드인 경우 삭제되지 않은 노드가 나올 때까지 모두 버림
      • 삭제 대상 노드 등장 시 삭제
    • 모든 연산이 끝난 후에도 남아있는 동기화 되지 않은 노드가 있을 수 있기 때문에 각 힙의 false로 되어있는 값들은 버려주어 동기화 시킴

 

 

[코드]

import sys
import heapq

for T in range(int(sys.stdin.readline())):
    k = int(sys.stdin.readline())
    visited = [False] * k
    maxH, minH = [], []
    for i in range(k):
        operation, n = sys.stdin.readline().split()
        n = int(n)

        if operation == 'I':
            heapq.heappush(minH, (n, i))
            heapq.heappush(maxH, (-n, i))
            visited[i] = True
        elif n == 1:
            while maxH and not visited[maxH[0][1]]:
                heapq.heappop(maxH)
            if maxH:
                visited[maxH[0][1]] = False
                heapq.heappop(maxH)
        else:
            while minH and not visited[minH[0][1]]:
                heapq.heappop(minH)
            if minH:
                visited[minH[0][1]] = False
                heapq.heappop(minH)
    while minH and not visited[minH[0][1]]:
        heapq.heappop(minH)
    while maxH and not visited[maxH[0][1]]:
        heapq.heappop(maxH)
    print(-maxH[0][0], minH[0][0]) if maxH and minH else print("EMPTY")