문제는 여기!
heapq 안쓰고 구현해보려고?
일단 python으로 힙을 만들려면, 직접 구현할 수도 있지만 기본 제공되는 heapq 모듈을 써주면 편하다.
기본이 min heap으로 구현되어 있길래, 처음엔 sort 메서드에 함수나 람다로 정렬 기준을 정해주는 것과 같은 요령으로 아래와 같은 구현이 가능할 줄 알았다.
heapq.heapify(my_heap, lambda x: -x)근데 해당 구현체에는 그런 기능이 없고, heapify 할 때 힙의 구성 요소가 iterable하면 맨 앞의 요소(이하 key)만 보고 수행한다는 점을 활용해야 한다. 즉, 그냥 enqueue할 때 -1을 곱해 가장 큰 수가 가장 작은 음수로써 힙의 루트 쪽에 위치하게 만들고, dequeue할 때는 다시 -1을 곱해서 원래의 값을 가져 오는 식으로 구현했다.
또, 이건 특히 파이썬을 쓰면서 엄청 고생했던지라 항상 확인하면서 써왔던 건데,, 함수의 signature를 보면 알 수 있듯 반환값이 None이다. 즉, heapify, heaqppush, heappop과 같은 요소들이 받는 리스트 원본에 해당 작업들을 수행하는 것이므로, 원본을 보존해야 한다면 list를 deep copy해서 써야 된다.
삽질 1 : 시간 복잡도 문제
Max heap을 만들어서 최솟값 삭제가 발생할 때 max heap에도 반영하고, 최댓값 삭제가 발생할 때 min heap에도 반영해야겠다는 생각까지는 했다. 문제는 그걸 매 pop 작업마다 min heap, max heap 리스트의 remove 메서드를 써서 했다는 건데,, 이렇게 하면 앞에서부터 삭제할 대상을 선형 탐색 해야 하기 때문에 시간 복잡도가 O(N)이 나온다.
삽질 2 : heap의 장점을 활용하기
그래서 한 이틀 머리 싸매다가 안되겠다 싶어서 다른 분 풀이를 실눈 뜨고 봤다. 삭제 연산을 동기화 해야 하는건 맞는데, 그걸 리스트에 직접 하는게 아니라 내쪽(여기서는 min heap이라 하자)에서 삭제했다는 정보를 어딘가에 저장해놨다가, 반대쪽(max heap)에서 삭제하기 전에 몽땅 제거해주는 방법을 쓰고 있었다.
이게 왜 가능하나면, min heap과 max heap이 각각 루트(index=0)에 최솟값과 최댓값을 항상 저장해 놓기 때문이다. 만약 min heap에서 삭제를 수행한 다음 삭제했다고 흔적만 남겨 놓으면, max heap은 그 반대편에서부터 삭제하기 때문에 삭제 처리를 하기 전에 삭제 처리된 수가 루트에 발견되지 않을 때까지 heap 구조를 유지하면서 삭제해주면 된다!
한쪽 heap에서 삭제되었지만 그 반대쪽 heap에서 삭제되지 않은 노드를 유령 노드 라고 해보겠다.
이걸 수도 코드로 표현하자면,,
ghost_nodes = {{ 유령 노드 정보를 저장할 저장소, O(1)이면 좋곘지? }}
if max heap 삭제:
while max heap의 루트에 유령 노드가 더 나타나지 않을 때까지:
max heap에서 pop 수행
max heap에서 타겟 삭제
min heap에서 유령 노드를 삭제할 수 있도록 ghost_nodes에 *타겟 추가*
else min heap 삭제:
while min heap의 루트에 유령 노드가 더 나타나지 않을 때까지:
min heap에서 pop 수행
min heap에서 타겟 삭제
max heap에서 유령 노드를 삭제할 수 있도록 ghost_nodes에 *타겟 추가*,,대강 이런 형태가 될 것이다.
휘유! 이제 제대로 풀리겠지,,?
삽질 3 : 문제를 똑바로 읽자.
위 코드에는 문제가 있다. 만약 같은 수가 연달아서 heap의 꼭대기에 있었고, 반대쪽 힙에서 그 수를 한 번만 삭제했다면? 삭제 동기화 작업 중에 의도치않게 우루루 죄없는 숫자들까지 삭제가 되어 버린다. 그럼 ghost_nodes에서 동기화가 수행될 때마다 유령 노드를 삭제해주면 되지 않을까?
# O(1) 달성을 위해 set을 사용했음
ghost_nodes = set()
if max heap 삭제:
while max heap의 루트에 유령 노드가 더 나타나지 않을 때까지:
max heap에서 pop 수행
**ghost_nodes에서 유령 노드를 삭제**
max heap에서 타겟 삭제
min heap에서 유령 노드를 삭제할 수 있도록 ghost_nodes에 타겟 추가
else min heap 삭제:
while min heap의 루트에 유령 노드가 더 나타나지 않을 때까지:
min heap에서 pop 수행
**ghost_nodes에서 유령 노드를 삭제**
min heap에서 타겟 삭제
max heap에서 유령 노드를 삭제할 수 있도록 ghost_nodes에 타겟 추가시간 복잡도 최소화를 위해 ghost_nodes의 자료형을 set으로 정했고, ghost_nodes에서 유령 노드를 삭제하는 코드를 넣었다. 그럼,, 돌아갈까?
삽질 4 : 반대쪽에서 여러번 삭제됐다면?
이번엔 정확히 반대 상황의 문제가 발생한다. 만약 min heap의 꼭대기와 그 아래에 같은 수가 두 번 반복되어 두 개 다 삭제 요청이 들어온다고 하더라도, ghost_nodes에는 1번의 삭제만 기록되기 때문에 이어서 max heap에서 pop 요청이 발생한다면 한 번의 삭제 동기화만 발생한다.
그렇기 때문에 ghost_nodes에 어떤 수가 삭제 대상인지 기록하는게 아니라, 몇 번째로 삽입된 노드인지를 기록한 뒤 동기화 과정에서 루트에 해당 명령어 번호가 발견되지 않을 때까지 삭제 동기화를 수행해 주어야 한다. 휘유!
물론 ghost_nodes를 list로 사용하는 식으로 구현할 수도 있겠지만, 그러기엔 선형 탐색이 요구되므로 시간 복잡도 측면에서 비효율적이다.
마지막 삽질 : 동기화 확실히 끝내주기
최대한 내 힘으로 풀고 싶어서 실눈 뜨고 솔루션을 봤더니 결국 하나를 놓쳤다.
위의 상황은 모두 한쪽 heap에서 삭제가 발생한 다음, 반대쪽 heap에서의 동기화가 반드시 발생함을 전제로 문제를 해결했지만 만약 그렇지 않다면 어떨까? 이를테면 맨 마지막 min heap에서의 삭제를 수행했지만 더이상 max heap에서 삭제가 요청되지 않아 동기화 상태가 깨져버린 것이다.
이를 위해 모든 push-pop 명령어의 처리가 끝난 다음 마지막으로 각 heap의 상부에 위치해 있을 유령 노드를 모두 빼주어야 한다.
코드
from typing import List, Tuple, Set
from sys import stdin
import heapq
input = stdin.readline
def solution(commands: List[Tuple[str, int]]) -> None:
# (저장된 숫자, insert된 cmd_idx)를 저장함 (heapq는 맨 앞 요소만 Key로 씀)
min_heap: List[(int, int)] = []
max_heap: List[(int, int)] = []
# 삭제가 발생한 명령어의 번호를 저장할 set
deleted_nums: Set[int] = set()
for cmd_idx, (cmd, num) in enumerate(commands):
# 각 힙에 heapify를 수행하며 값 넣어주기
if cmd == "I":
# max heap의 경우 key값에 -1을 곱해 가장 큰 음수가 맨 위로 오게 함
heapq.heappush(max_heap, (-num, cmd_idx))
heapq.heappush(min_heap, (num, cmd_idx))
else:
# 최댓값 빼기
if num == 1:
# min_heap에서 삭제 처리된 요소가 있을 수 있으므로 삭제로 동기화
while max_heap and max_heap[0][1] in deleted_nums:
deleted_nums.remove(max_heap[0][1])
heapq.heappop(max_heap)
if max_heap:
popped_num, popped_i = heapq.heappop(max_heap)
# 여기선 안쓰지만, max_heap에서 값을 꺼내서 저장할 때는
# 다시 -1을 곱해 복구해야 함
# popped_num *= -1
deleted_nums.add(popped_i)
# 최솟값 빼기
else:
# max_heap에서 삭제 처리된 요소가 있을 수 있으므로 삭제로 동기화
while min_heap and min_heap[0][1] in deleted_nums:
deleted_nums.remove(min_heap[0][1])
heapq.heappop(min_heap)
if min_heap:
popped_num, popped_i = heapq.heappop(min_heap)
deleted_nums.add(popped_i)
# 삭제 동기화가 발생하지 않았을 수 있으므로 마지막에 따로 수행해줌
while max_heap and max_heap[0][1] in deleted_nums:
heapq.heappop(max_heap)
while min_heap and min_heap[0][1] in deleted_nums:
heapq.heappop(min_heap)
# 각 힙의 정점에 있는 노드가 최대/최솟값임
largest = None if not max_heap else -max_heap[0][0]
smallest = None if not min_heap else min_heap[0][0]
# 최솟값이 없으면 최댓값도 없으므로 smallest로만 판단해도 됨
if smallest is None:
print("EMPTY")
# 최솟값이 있으면 최댓값도 있으므로 둘 다 출력
else:
print(largest, smallest)
if __name__ == "__main__":
tc = int(input())
for i in range(tc):
commands = []
num_of_commands = int(input())
for j in range(num_of_commands):
cmd, num = input().split()
commands.append((cmd, int(num)))
solution(commands)코드에 주석으로 설명하는게 더 좋을 것 같아서 따로 설명은 안 남겨 놓겠다.
