[Python] 7662. 이중 우선순위 큐(골4) / 최소힙과 최대힙

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

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

7662번: 이중 우선순위 큐

---

2. 핵심 아이디어

 

먼저 본 문제를 풀기 위해서는 최소힙과 최대힙의 기본개념을 알고 있어야 한다.

 

이 개념을 모른다면 먼저 다음링크를 통해 최소힙과 최대힙의

기본 개념을 익혀보자

https://juhee-maeng.tistory.com/94

[자료구조] 힙(Heap)이란? 최대힙(Max Heap)과 최소힙(Min Heap)

 

 

이 문제는 우선순위 큐를 최소, 최대 두가지 모두 운용해야 한다.

특히 입력이 한번에 주어지는 것이 아니라 언제 주어질지 모르기 때문에

그때마다 입력을 받게되면 리스트나 덱의 경우 시간복잡도에서 큰 손해를 본다.

 

따라서, 정렬이 아닌 heapq문제라는 점을 알 수 있다.

 

그럼 이 문제는 어떻게 해결할 수 있을까?

 

풀이 과정의 주요요소는 다음과 같다.

- min_heapq과 max_heapq을 둘다 정의한다.

- 입력이 주어졌을 때, 순서를 key로 두 q에 모두 넣는다.

- 출력: 1이면 max_heap에서 유효한 최대값 하나를 pop한다.

- 출력 : -1이면 min_heap에서 유효한 최소값 하나를 pop한다.

 

#여기서 유효한 숫자란 아직 상대 q에서 처리되지 않은 숫자를 뜻한다.

 

- min_heapq과 max_heapq에 숫자가 있다면 각각 최대, 최소값을 출력한다.

- 둘중 하나라도 비어있다면 empty를 출력한다.

---

예를 들어 첫번째 테스트 케이스를 예시로 들어보겠다.

 

먼저 min_heap과 max_heap을 정의한다.

min_heap, max_heap =[], []

 

그리고 각 숫자가 처리되었는지를 판단한 1차원 visited 배열을 선언한다.

vistied=[Fase] *1000001 

#최대 명령어 수가 1000000이므로

 

7
I 16
I -5643
D -1
D 1
D 1
I 123
D -1

 

첫번째 test case의 경우 7개의 입력이 주어진다.

 

0번째 입력인 I 16을 보자.

입력을 받으면 min heap과 max_heap에 모두 key인 입력순서(0)와 함께 넣는다.

 

min_heap = [ ( 16, 0) ]

max_heap= [ (-16, 0) ]

 

이제 0번째는 아직 출력되지 않은 숫자(처리되지 않은 숫자)이다.

따라서 아직 숫자가 유효함을 나타내기 위해 visited[key]를 True로 갱신한다.

 

visited[0]=True

=> visited= [True, False , False, False.....]

---

 

1번째 입력인 I -5643 을 보자.

 

입력을 받으면 min heap과 max_heap에 모두 key인 입력순서(1)와 함께 넣는다.

 

min_heap = [ (-5643,1) ( 16, 0) ]

max_heap= [ (-16, 0) , (5643,1) ]

 

이제 1번째는 아직 출력되지 않은 숫자(처리되지 않은 숫자)이다.

따라서 아직 숫자가 유효함을 나타내기 위해 visited[key]를 True로 갱신한다.

 

visited[1]=True

=> visited= [True, True, False , False, False........]

---

2번째 입력인 D -1  을 보자.

 

이번엔 최소값을 출력하는 입력어다.

min_heap에서 유효한 하나를 pop하자.

 

min_heap = [ (-5643,1) ( 16, 0) ]

max_heap= [ (-16, 0) , (5643,1) ]

 

 

min_heap의 첫번째요소인 1번째 key는 아직 True 즉 pop되지 않은 유효한 숫자이다.

=> visited= [True, True, False , False, False........]

 

따라서 min_heap의 첫번째를 처리했음을 나타내기 위해

visited[1]을 False로 갱신하고

=> visited= [True, False, False , False, False........]

 

min_heapq을 pop한다.

min_heap = [ ( 16, 0) ] => pop (-5643,1)

max_heap= [ (-16, 0) , (5643,1) ]

---

3번째 입력인 D 1  을 보자.

 

이번엔 최대을 출력하는 입력어다.

max_heap에서 유효한 하나를 pop하자.

 

min_heap = [ ( 16, 0) ]

max_heap= [ (-16, 0) , (5643,1) ]

 

 

max_heap의 첫번째요소인(-16,0)의  key인 0번째는 아직 True

즉 pop되지 않은 유효한 숫자이다.

 

=> visited= [True, False , False, False........]

 

따라서 max_heap의 첫번째를 처리했음을 나타내기 위해

visited[0]을 False로 갱신하고

=> visited= [ False, False , False, False........]

 

max_heapq을 pop한다.

min_heap = [ ( 16, 0) ]

max_heap= [  (5643,1) ] => (-16, 0)  

 

---

4번째 입력인 D 1  을 보자.

 

이번에도 최대을 출력하는 입력어다.

max_heap에서 유효한 하나를 pop하자.

 

min_heap = [ ( 16, 0) ]

max_heap= [  (5643,1) ]

 

max_heap의 첫번째요소인(5643,1)의  key인 1번째는 False

즉 이미 min_heap에서 처리된 유효하지 않은 숫자이다.

 

=> visited= [False, False , False, False........]

 

따라서 (5643,1)은 이미 처리된 쓰레기 노드이다.

쓰레기 노드는 pop해준다.

 

min_heap = [ ( 16, 0) ]

max_heap= [ ] = >  (5643,1) 

 

이제 더이상 검사할 노드가 max_heap에 없다.

그럼 그냥 패스

---

5번째 입력인 I 123을 보자.

입력을 받으면 min heap과 max_heap에 모두 key인 입력순서(5)와 함께 넣는다.

 

min_heap = [ ( 16, 0) ,   (123,5)  ]

max_heap= [   (123,5)  ] 

 

이제 5번째는 아직 출력되지 않은 숫자(처리되지 않은 숫자)이다.

따라서 아직 숫자가 유효함을 나타내기 위해 visited[key]를 True로 갱신한다.

 

visited[5]=True

=> visited= [  False , False, False.  False , False, True, False , False, False.....]

---

6번째 입력인 D -1  을 보자.

 

이번엔 최소값을 출력하는 입력어다.

min_heap에서 유효한 하나를 pop하자.

 

min_heap = [ ( 16, 0) ,   (123,5)  ]

max_heap= [   (123,5)  ] 

 

 

min_heap의 첫번째요소인 (16,0) 의 key 0 는 False

이미 max_heap에서 pop된 숫자로 유효하지 않다.

=> visited= [  False , False, False.  False , False, True, False , False, False.....]

 

따라서 쓰레기 노드이다. 그럼 그냥 pop해준다.

min_heap = [  (123,5)  ] => pop ( 16, 0) ,  

max_heap= [   (123,5)  ] 

 

 

다음 min_heap의 첫번째요소인 (123,5) 의 key 0 는 True

즉 pop되지 않은 유효한 숫자이다.

 

min_heap = [  (123,5)  ]

max_heap= [   (123,5)  ] 

=> visited= [  False , False, False.  False , False, True, False , False, False.....]

 

따라서 visited[5]을 False로 갱신하고

=> visited= [  False , False, False.  False , False, False, False , False, False.....]

 

min_heapq을 pop한다.

min_heap = [   ] => pop (123,5) 

max_heap= [   (123,5)  ] 

---

이렇게 해서 전체 명령어를 하나씩 모두 완료했다.

 

그럼 min_heap과 max_heap을 살펴본다.

min_heap과 max_heap에 요소들이 있으면 하나씩 pop한다.

 

min_heap = [   ]

max_heap= [   (123,5)  ] 

 

그러나, min_heap이 비어있다.

따라서 EMPTY 출력...

 

그럼 이제 이 과정을 코드로 옮겨보자.

 

---

3. 코드

import heapq

for _ in range(int(input())):

    n= int(input())
    min_q, max_q=[],[]
    visited=[False] *1000001

    for i in range(n):
      a,b= input().split()
      if a=="I":
        heapq.heappush(min_q, (int(b),i))
        heapq.heappush(max_q, (-(int(b)),i))
        visited[i]=True
      elif a=="D":
        if b=="1":
          while(max_q and visited[max_q[0][1]]==False):
            heapq.heappop(max_q)
          if max_q:
            visited[max_q[0][1]]=False
            heapq.heappop(max_q)
        else:
          while(min_q and visited[min_q[0][1]]==False):
            heapq.heappop(min_q)
          if min_q:
            visited[min_q[0][1]]=False
            heapq.heappop(min_q)

    while(max_q and visited[max_q[0][1]]==False):
            heapq.heappop(max_q)
    while(min_q and visited[min_q[0][1]]==False):
            heapq.heappop(min_q)
            
    if min_q and max_q:
      print(-max_q[0][0], min_q[0][0])
    else:
      print("EMPTY")

---

4.배운 점

max_heap과 min_heap의 정보를 서로 알아볼 수 있도록 visited 배열을 활용하는 것이 가장 중요했다.

처음에는 min_heap을 max_heap으로 변환시키는 과정을 통해 문제를 풀이했는데 역시나 시간초과가 떴다.

 

heapq는 되도록 배열 자체를 변환시키기보다

서로 다른 정렬을 가진 min/max를 각각 만들어주고

그 두 자료구조가 소통하면서 삽입, 출력에만 시간을 할애하는 것이 훨씬 이득이라는 점을 잊지 말자.