[백준7662&파이썬] 이중 우선순위 큐를 만들고 관리하기(중복값 처리에 대해 항상 생각하자)

# 문제

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

7662번: 이중 우선순위 큐

 

# 코드

'''
  - 정렬을 이용한 풀이방법은 시간초과
    - 정렬 O( k * log N)
  - 힙을 이용해서 풀고 싶다
    - 힙을 두개이용하는 방법 말고 없을까?
    - nlargeset 풀이방법을 이용
  - 중복값이 두번 들어올 수 있다.
    - 이럴경우 dict을 True / False 로 관리하면 관리 할 수 없게 된다.
    - 고유 ID값을 주고 그걸 사용하자.
'''
import sys
from heapq import *
from collections import defaultdict

T = int(sys.stdin.readline().strip())


def solve():
  k = int(sys.stdin.readline().strip())
  minheap = list()
  maxheap = list()
  used = dict()

  for id in range(k):
    operation, num = sys.stdin.readline().split()
    num = int(num)
    if operation == "I":  # 삽입 명령
      heappush(minheap, (num, id))
      heappush(maxheap, (-num, id))
      used[id] = False

    if operation == "D":  # 삭제 명령
      if len(minheap) > 0:
        if num == -1:  # -1 일시 최소값을 뽑아야함
          while len(minheap) > 0:
            poped, id = heappop(minheap)
            if used[id] == False:
              used[id] = True
              break

        if num == 1:  # 1 일시 최대값을 뽑아야함
          while len(maxheap) > 0:
            poped, id = heappop(maxheap)
            if used[id] == False:
              used[id] = True
              break

  # 사용했던 값 제거 ( 양쪽 균형 맞춰 줘야 함 )
  while len(maxheap) > 0:
    if used[maxheap[0][1]] == True:
      heappop(maxheap)
    else:
      break

  while len(minheap) > 0:
    if used[minheap[0][1]] == True:
      heappop(minheap)
    else:
      break
  # print(maxheap,minheap)
  if len(minheap) == 0 and len(maxheap) == 0:
    print("EMPTY")
  else:
    print(maxheap[0][0] * -1, minheap[0][0])


for _ in range(T):
  solve()

# 풀이

• 첫번째로는 리스트(list)를 하나 만들고 sort을 오름차순,내림차순 두가지의 경우로 나누어 하며 맨뒤를 pop해줬다. 시간초과
• 두번째로는 nlargeset를 사용하여 풀었다. 시간초과
• 세번째로는 딕셔너리(dict)을 이용하여 minheap, maxheap을 만들고 둘을 관리해주는 방법을  사용했다. dict을 통해서 입력받았던 num을 이미 사용했던 값인지 여부를 가렸다. 틀림
• 세번째 풀이방법이 맞을거라 생각했지만 틀렸고, 그 이유를 고민했을때 중복되는 값이 들어왔을때에 대한 처리를 생각하지 못했다. 사실 중복값이 들어올거라고는 생각은 했지만, 삭제된 후에 들어온다고 생각했다. 즉 힙안에 중복되는 값이 두개가 들어있을거라는 생각을 못했다. 이럴경우 dict을 이용한 세번째 풀이방법이 틀리는 명확한 이유가 된다.
• 네번째 풀이방법으로는 들어오는 값을 통해 dict을 관리하는 것이 아닌, 고유의 id값 처럼 활용해서 used를 결정했다. 이렇게 푸니 정답 처리 됐다.