백준 - 1655. 가운데를 말해요

[백준] 1655. 가운데를 말해요

Link 골드 2티어 문제

문제

백준이는 동생에게 “가운데를 말해요” 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.

출력

한 줄에 하나씩 N줄에 걸쳐 백준이의 동생이 말해야 하는 수를 순서대로 출력한다.

예제 입력 1

7
1
5
2
10
-99
7
5

예제 출력 1

1
1
2
2
2
2
5

풀이

Goal은 정수가 하나씩 입력될 때 마다 그때의 중간값을 구하는 문제라고 할 수 있다.

아무런 제약조건이 없을 경우, 단순히 Append와 Sorting을 반복한다면 쉽게 풀리는 문제이긴 하지만 0.1초라는 시간 제한이 있어 최적화해야하는 문제이다.

계산 복잡도에 영향을 주는 요소를 파악하면, 결국 Sorting하는 부분의 복잡도를 줄여야만 한다.

사실 이미 Python의 리스트 객체의 Sorting 알고리즘은 Quick 정렬을 사용하고 있어 이미 빠르기 때문에 정렬 알고리즘 자체를 변경하는 것은 무의미하다 (아닐수도).

고민고민하다가 결국 정답을 찾아봤는데 해법은 Heap를 사용하는 것이었다.

Heapq는 최댓값과 최솟값을 빠르게 찾기위해 고안된 완전 이진 트리 https://velog.io/@gnwjd309/data-structure-heap

노드를 삽입할 때 최소 Heap의 경우 자식 노드보다 부모 노드의 값이 작아야한다는 규칙에 따라 트리를 형성한다.

따라서 최소 Heap이라고 한다면 최솟값은 항상 트리의 루트노드가 되어서 최솟값에 접근하는 연산의 시간복잡도는 \(O(1)\)이 된다.

대신 삽입과 삭제의 시간복잡도는 리스트가 \(O(1)\)이고 Heap은 \(O(log n)\)이다.

허나 Heap이 삽입과 동시에 Sorting이 이루어지고, List의 Quick sort의 시간복잡도는 \(O(n log n)\) 에서 최악의 케이스에서는 \(O(n^2)\)이 되기 때문에 Heap을 쓰는것이 훨씬 효율적인 방식이 된다.

Heap 하나를 써서 값을 계속 넣고 그 중간값을 출력해도 괜찮겠지만 (안해봤음), 트리의 높이가 h라고 할 때, \(O(h)\)의 시간복잡도가 있다.

그래서 하나는 최대힙, 하나는 최소힙을 사용하여 최대힙의 최대값과 최소힙을 생성하고 두 힙의 길이를 일정하게 맞춰가며 삽입한다면 중간값을 출력할 수 있다.

1. left_heap과 right_heap을 초기화한다. left_heap은 최대 힙, right_heap은 최소 힙이다.
   • 파이썬의 Heapq 내장 클래스는 최소힙만 제공하기 때문에 성분들에 -1을 곱해줘서 최대 힙과 같이 동작하도록 만든다. 나중에 값에 접근할 때는 다시 -1을 곱해줘야한다는 것을 명심하자.
2. 정수 r를 입력받는다.
3. left_heap과 right_heap의 길이가 같으면 left_heap에 삽입하고 아니면 right_heap에 넣는다. (left_heap에 항상 먼저 들어가게 됨)
4. left_heap[0]은 left_heap의 최대값, right_heap[0]은 right_heap의 최소값으로, left_heap의 최대값이 right_heap의 최소값보다 크다면 두 값을 Pop하여 서로 바꿔준다.
5. left_heap의 최대값을 출력한다.
6. 이를 N번 반복한다.

import heapq
import sys

# 이게 없으면 시간초과가 날수도 있다고..
N =  int(sys.stdin.readline())

left_heap = []
right_heap = []

for i in range(0, N):
    r = int(sys.stdin.readline())
    len_lh = len(left_heap)
    len_rh = len(right_heap)

    if len_lh == len_rh:
        heapq.heappush(left_heap, r * -1)
    else:
        heapq.heappush(right_heap, r)
    
    if left_heap and right_heap and left_heap[0] * -1 > right_heap[0]:
        left_max = heapq.heappop(left_heap)
        right_min = heapq.heappop(right_heap)
        heapq.heappush(left_heap, right_min * -1)
        heapq.heappush(right_heap, left_max * -1)
    print(left_heap[0] * -1)