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

문제

가운데를 말해요

풀이

1. 문제조건 해석

   리스트의 원소가 하나씩 주어지고 주어질 때마다 중간값 찾는 문제다.

2. 알고리즘

   처음에는 리스트의 정렬을 유지하며 삽입하는 방법으로 접근했다.

   • 순차 탐색을 통해 삽입 인덱스 찾으면 $N^2$로 시간 초과 발생했다.
   • 이분 탐색 $N\log{N}$을 이용해서 시간 내 성공했다.

   최대 힙 하나, 최소 힙 하나를 이용해서 푸는 것이 문제 의도인 것 같다. 시간이 훨씬 빨랐다.

   • 최대 힙의 루트가 중간값이며
   • 최대 힙의 루트는 항상 최소 힙의 루트보다 작다
   • 노드 수가 같다면 최대 힙 우선으로 노드를 삽입한다

3. 코드

# 2. 이분 탐색으로도 시도해 보자 (nlogn)
from sys import stdin
input = stdin.readline
def binary_search(nums, target):
    left = 0
    right = len(nums)
    while left < right:
        mid = (left+right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] > target:
            right = mid
        else:
            left = mid+1
    return right

n = int(input().rstrip)
nums = []
for step in range(n):
    num = int(input().rstrip)
    insert_idx = 0
    
    insert_idx = binary_search(nums, num)
    
    nums.insert(insert_idx, num)
    # print(nums)
    print(nums[(len(nums)-1)//2])

# 위 방법으로 nlogn 만에 성공한다.
# 그러나 힙을 이용하면 더 빠르게 해결할 수 있을 것 같다.

from sys import stdin
import heapq
input = stdin.readline
def heap_solution(min_heap, max_heap, target):
    # max_heap의 루트 노드가 중간값
    # max_heap의 루트는 항상 min_heap의 루트보다 같거나 작아야 한다
    if len(max_heap) == len(min_heap):
        heapq.heappush(max_heap, -target)
    else:
        heapq.heappush(min_heap, target)
    if min_heap and -max_heap[0] > min_heap[0]:
        max_insert = -heapq.heappop(min_heap)
        min_insert = -heapq.heappop(max_heap)
        
        heapq.heappush(max_heap, max_insert)
        heapq.heappush(min_heap, min_insert)

n = int(input().rstrip())
min_heap, max_heap = [], []
for step in range(n):
    num = int(input().rstrip())
    
    heap_solution(min_heap, max_heap, num)
    print(-max_heap[0])