[백준 - Python] 7662 - 이중 우선순위 큐

0.  문제 링크

 

 

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

7662번: 이중 우선순위 큐

---

1.  풀이 방법

 

 

1. 파이썬에는 우선순위 큐를 위한 모듈이 있음. 해당 모듈을 사용하면 최솟값 힙, 최댓값 힙을 구현할 수 있음
2. 최솟값 힙, 최댓값 힙을 만들었음
   1. 여기서 생기는 문제점은 최솟값 힙에서 삭제한 숫자가 최댓값 힙에는 적용되지 않는다는 문제점임
3. 따라서 최솟값 힙에서 삭제한 숫자를 따로 저장하는 딕셔너리를 만들었음. 최댓값 힙에도 마찬가지로 생성함
   1. 만약 최솟값 힙에서 숫자 k를 n번 삭제하면, 최댓값 힙에서는 숫자 k가 n번 나올때까지 무시함
   2. 이후 n + 1번째 k에 대해서 연산을 수행함
4. 마지막으로 출력도 똑같은 logic을 사용하여 해결하였음

---

2.  코드

 

 

import sys
import heapq
from collections import defaultdict
input = sys.stdin.readline


def logic(힙, 힙뺀거, 신호):
    try:
        숫자 = (1, -1)[신호] * heapq.heappop(힙)
        while 힙뺀거[숫자] > 0:      # 최댓값 힙에서 해당 값을 1번 이상 뺀 적이 있다면
            힙뺀거[숫자] -= 1        # 동일한 숫자를 2~3번 뺐을 수도 있으니, 1만 빼서 중복 관리
            숫자 = (1, -1)[신호] * heapq.heappop(힙)
        return 숫자
    except IndexError:
        return 'F'


if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        minheap = []        # 최솟값 힙
        maxheap = []        # 최댓값 힙
        minheap_del = defaultdict(int)      # 최솟값 힙에서 어떤 값을 뺐는지
        maxheap_del = defaultdict(int)      # 최댓값 힙에서 어떤 값을 뺐는지
        cnt = 0        # 현재 힙에 있는 숫자의 개수
        k = int(input())
        for _ in range(k):
            inst, num = input().split()
            num = int(num)
            if inst == 'I':
                heapq.heappush(minheap, num)
                heapq.heappush(maxheap, -num)
                cnt += 1
            else:
                if cnt > 0:     # 들어간 게 더 많을 때
                    if num == -1:
                        minheap_del[logic(minheap, maxheap_del, 0)] += 1       # 최솟값 힙에서 해당 숫자를 뺐음
                    else:
                        maxheap_del[logic(maxheap, minheap_del, 1)] += 1
                    cnt -= 1       # 힙에서 숫자 하나를 뺐으므로, cnt_를 -1함

        if cnt > 0:
            min_flag = logic(minheap, maxheap_del, 0)
            max_flag = logic(maxheap, minheap_del, 1)

            if max_flag == 'F':
                print(min_flag, min_flag)
            elif min_flag == 'F':
                print(max_flag, max_flag)
            else:
                print(max_flag, min_flag)
        else:
            print('EMPTY')

---

3.  마무리

 

 

문제가 3일 동안 계속 92%에서 틀려서 멘탈이 터졌음

오기가 생겨서 답지도 안 보고 코드 하나하나 분석했음

설마 출력이 문제인가 싶어서, 모든 힙을 세트로 만든 다음에 교집합을 구한 후에 최솟값, 최댓값을 구해봄

그랬더니 맞아서 출력 부분을 수정함