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

www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

• 문제유형 : 우선순위큐, 자료구조
• 문제 풀이

neomindstd.github.io/%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/boj7662/

[백준/파이썬] 7662번 이중 우선순위 큐 풀이

• 처음에 우선순위 큐 하나를 두고(최소힙), 최소값삭제는 최소힙그대로 빼고, 최대값 삭제일때는 최소힙의 모든 원소에 접근하고 부호를 바꿔서 다시 집어넣어 최대힙으로 만든뒤, 최댓값을 삭제하고,,, 다시 최소힙일때는 부호를 바꿔서 최소힙으로 바꿔주는 형식으루 구현함 -> 구현은 됫는데 효율 쓰뤡이 ㅇㅇ 당연히 시간초과
• 최소힙과 최대힙 2개를 두고 쓰는방법을 맨처음 시도했는데 도무지 두 힙을 동기화시키는 방법이 생각나지 않아서 결국 힙한개로 풀었는데 역시나 2개힙을 사용하는거였다...
• 자세한 설명은 위 블로그가 너무 잘 설명해주셔서 생략하도록 하겠다.
• 핵심은 튜플형태로 힙에 추가하는데 이때 튜플의 2번째 원소에 id값을 넣어주어 이 키값을 토대로 최소힙과 최대힙을 동기화 시켜주는것이였다.

 

• 정답코드 

import sys
import heapq
input = sys.stdin.readline


test = int(input())
for _ in range(test):
    max_heap, min_heap = [], []
    visit = [False] * 1_000_001

    order_num = int(input())

    for key in range(order_num):
        order = input().rsplit()
        if order[0] == 'I':
            heapq.heappush(min_heap, (int(order[1]), key))
            heapq.heappush(max_heap, (int(order[1]) * -1, key))
            visit[key] = True #True이면 어떤 힙에서도 아직 삭제되지 않은 상태

        elif order[0] == 'D':
            if order[1] == '-1': #삭제연산시, key값을 기준으로 해당 노드가 다른힙에서 삭제된 노드인가를 먼저 판단한다.
                # 이미 상대힙에 의해 삭제된 노드인경우 삭제되지 않은 노드가 나올때까지 계쏙 버리다가 이후 삭제대상노드가 나오면 삭제한다.
                while min_heap and not visit[min_heap[0][1]]: # visit이 False일떄 -> 해당노드가 삭제된상태
                    heapq.heappop(min_heap) # 버림 (상대힙에서 이미 삭제된노드이므로)
                if min_heap:
                    visit[min_heap[0][1]] = False # visit이 Ture엿으므로 False로 바꾸고 내가 삭제함
                    heapq.heappop(min_heap)
            elif order[1] == '1':
                while max_heap and not visit[max_heap[0][1]]: #이미 삭제된 노드인경우 삭제되지 않은 노드가 나올때까지 모두 버린다.
                    heapq.heappop(max_heap)
                if max_heap:
                    visit[max_heap[0][1]] = False
                    heapq.heappop(max_heap)

# 모든 연산이 끝난후에도 ㅅ쓰레기 노드가 들어있을수 있으므로, 결과를 내기전 모두 비우고 각 힙의 첫번째 원소값을 출력한다. 
    while min_heap and not visit[min_heap[0][1]]:
        heapq.heappop(min_heap)
    while max_heap and not visit[max_heap[0][1]]:
        heapq.heappop(max_heap)

    if min_heap and max_heap:
        print(-max_heap[0][0], min_heap[0][0])
    else:
        print('EMPTY')

---

번외로 파이썬 힙큐 모듈에 대해서 완전 공부하게 된 문제였는데 까먹지 않기위해 간단히 정리해야겠다.

import heapq

• 힙큐 모듈은 우선순위 큐를 구현하기위한 자료구조인 힙의 구현을 제공한다.
• (최소)힙은 가장 작은요소가 항상 루트인 heap[0]이다.
• 힙큐 모듈은 리스트를 최소힙처럼 다룰 수 있도록 하기때문에, 빈 리스트를 생성한후 heapq의 함수를 호출할때마다 리스트를 인자에 넘겨야 한다.
• 이미 생성해둔 리스트가 있다면 heapify()함수를 통해 즉각적으로 힙 자료형으로 변환할 수 있다.
  •  내가 실수했던것
  • 빈 리스트 q에 heappush()로 하나씩 원소를 넣어 최소힙 q를 생성한다.
  • 이를 최대힙으로 바꾼답시고 어떤 리스트를 받아 리스트안의 모든 원소를 음수로 바꾸는 함수를 만들고, 이 함수에 q를 넣어 부호가 모두 바뀐 q를 최대힙이라고 생각했다.
  • 근데 이렇게 하면 예를들어 처음 q가 [1,2,3]이고 내가만든 함수를 통과한 q가 [-1.-2.-3]이라고할때, q와 연결된 최소힙의 상태는 (트리형태) 1-2-3에서 단지 해당 노드의 '값'만 바뀐 -1 -> -2 -> -3의 트리형태를 띄고있는것이다.. 그러니 여기서 heappop()을 하면 내가 기대햇던값 -3이 아닌 -1이 그대로 나오는것이다 (힙입장에선 루트노드가 항상 작으니까),,,
  • 만약 내가 했던 부호를 바꾼 리스트q로 최대힙을 만들고 싶었다면 다시 heappush()를 통해 부호가바뀐 리스트q의 원소를 하나씩 힙에 추가해 주거나 이미 생성해둔 리스트를 즉각적으로 힙자료형으로 변환할 수 있는 heapify()함수를 사용했어야한다.