❓1655번 : 가운데를 말해요
〽️ 문제 요약
숫자 N개가 하나씩 주어질 때마다 그 수를 포함하여 지금까지의 중간 값을 출력하면 되는 문제
🤨 접근법
수가 하나씩 입력될 때 마다 중간값을 알아야 한다. 그렇기 때문에 매번 수를 입력받을 때마다 대략적으로는 수들 끼리의 관계가 포함되도록 자료구조를 활용해야할 것 같다. 처음에는 하나의 힙을 활용하였다. 수를 여러번 뒤죽박죽 입력받아도 출력할 때는 최소값 혹은 최댓값을 우선으로 출력할수록 구현할 수 있기 때문에 문제를 해결할 수 있을 것이다.
내장 라이브러리인 heapq모듈의 heappush와 더불어 nsmallest 함수를 활용하였다. nsmallest(n, heap)는 heap에서 n번째로 작은 수 까지의 리스트를 반환해준다. 따라서 적절하게 중간값의 인덱스를 n에 지정해주고 n번째로 작은 수를 출력하도록 문제를 구현했었다.
하지만 이러한 방식으로는 시간 초과가 발생한다. 어쨌든 수를 중간값까지 무작정 heappop하는 시간 복잡도와 별 다를 게 없는 방법이었다. 다른 방법을 찾아야 했다.
계속 고민을 거듭한 결과 하나의 힙 혹은 리스트를 활용할 때에는 결국 중간 값을 찾기 위해서 리스트의 size만큼의 시간복잡도가 필요했다. 너무 하나의 자료구조를 활용하는 데에만 국한된 풀이를 생각했던 것 같다.
참고한 풀이는 두 개의 힙(left_heap, right_heap)을 활용하였다. left_heap은 최대 힙으로 구현하여 중간값 이하의 값을 관리하고, right_heap은 최소 힙으로 구현하여 중간값보다 큰 값을 관리하였다.
값을 입력받을 때 left_heap에 우선적으로 삽입하고, 이후에는 두 힙의 크기가 같아지도록 크기를 비교하여 삽입한다. 그리고 삽입 후 left_heap의 루트 노드가 right_heap의 루트 노드보다 크면 두 노드를 pop하고 교환하여 삽입해주는 작업을 거쳐야 한다.
left_heap은 중간값 이하의 값을을 관리하는 최대 힙이기 때문에 left_heap의 루트 노드는 항상 중간 값이어야 한다. 만일 하나의 노드를 삽입 후 left_heap의 루트 노드가 right_heap의 루트 노드보다 크다면 left_heap의 루트 노드는 중간값이 아니게 되기 때문에 두 값을 교환해줘야 한다.
따라서 매번 값을 삽입 후 위와 같은 작업을 거친 다음, left_heap의 루트 노드를 출력해주면 된다.
🔡 코드
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
N = int(input())
left_heap, right_heap = [], [] # left : 최대 힙, right : 최소 힙
answer = []
for i in range(N):
num = int(input())
if len(left_heap) == len(right_heap):
heappush(left_heap, (-num, num))
else:
heappush(right_heap, (num, num))
if right_heap and left_heap[0][1] > right_heap[0][1]:
left_root_value = heappop(left_heap)[1]
right_root_value = heappop(right_heap)[1]
heappush(left_heap, (-right_root_value, right_root_value))
heappush(right_heap, (left_root_value, left_root_value))
answer.append(left_heap[0][1])
for median in answer:
print(median)📚 고찰
자료구조를 응용하는 문제를 풀이할 때 늘 하나의 자료구조를 활용하는 데에만 국한된 풀이를 생각하는 버릇이 또 나온 것 같다. 일단은 여러 자료구조를 활용하는 데 필요한 메모리 측면에서의 한계를 생각하지 말고 하나의 자료구조를 활용한 풀이가 생각나지 않으면 두개, 세개… 를 활용해보자
