[백준 1655] 가운데를 말해요(Python) 우선순위 큐 풀이 방법

[문제]

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

[풀이]

정수를 하나씩 외칠때마다 동생은 지금까지 수중에서 중간값을 말해야 한다.

 

sol-1) 이진 탐색으로 풀었는데 시간초과 발생.. 

sol-2) 우선순위 큐로 접근하여 해결하였다. 

- 아이디어 : 중앙값 기준으로 왼쪽은 maxheap, 오른쪽은 minheap
- 중간값 기준으로 왼쪽에 맥스힙(작은 수 중에 제일 큰거), 오른쪽에 민힙(큰 수 중에 제일 작은 값 )
: 수를 정렬했다고 생각하면 쉬움
maxheap[0] <= 중간값 <= minheap[0]

 

[코드]

# sol-1 이진탐색
# import bisect
# import sys
#
# n = int(sys.stdin.readline())
# arr = []
# num = int(input())  # 첫 번째 숫자 받기
# arr.append(num)
# print(num)
# length = 1
#
# for _ in range(n-1):
#     num = int(sys.stdin.readline())
#     arr.insert(bisect.bisect_left(arr, num), num)  # 삽입할 인덱스(위치)와 삽입할 숫자
#     length += 1
#
#     if length % 2 == 0:
#         print(min(arr[length // 2 - 1], arr[length // 2]))
#     else:
#         print(arr[length // 2])


# sol-2 우선순위 큐
import heapq
import sys

n = int(sys.stdin.readline())
min_heap = []
max_heap = []  # 최대힙은 음수곱해줘야 하는거 잊지말기

for _ in range(n):
    temp = int(sys.stdin.readline())
    if len(min_heap) == len(max_heap):  # 먼저 우선적으로 왼쪽에 넣는다.
        heapq.heappush(max_heap, (-temp, temp))  # (우선순위, 값)
    else:
        heapq.heappush(min_heap, (temp, temp))

    if min_heap and min_heap[0][1] < max_heap[0][1]:  # maxheap[0] <= 중간값 <= minheap[0] 조건을 만족하도록 스왑
        right = heapq.heappop(min_heap)[1]
        left = heapq.heappop(max_heap)[1]
        heapq.heappush(min_heap, (left, left))
        heapq.heappush(max_heap, (-right, right))
    print(max_heap[0][1])  # 작은 값들 중에 큰값