[BOJ] 1655. 가운데를 말해요

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

 

문제: 백준이가 외치는 수들의 가운데 수를 매번 구하라.

 

문제 이해하기!!

우선순위 큐를 이용한 가운데 수 구하기 문제입니다.

최대 우선순위 큐와 최소 우선순위 큐를 동시에 이용해서 경계 값을 찾아내면 됩니다.

 

그래서 푼 방법은

1. T == 1인상황과 2 이상인 상황을 분리시킵니다.

2. 2인 상황에서 최소힙이 (지금까지 부른 수들의 갯수 // 2)보다 작으면 최대힙의 팝한 숫자나 현재 숫자를 최소힙에 넣어줍니다.

3. 반대로 최소힙이 (지금까지 부른 수들의 갯수 // 2)보다 크면 최소힙의 팝한 숫자나 현재 숫자를 최대힙에 넣어줍니다.

4. 매번 최소힙의 탑(arr[0])을 출력하면 됩니다.

 

코드:

from sys import stdin
import heapq
input = stdin.readline

T = int(input())
if T == 1:
    print(int(input()))
else:
    arr = [int(input())]
    print(arr[0])
    arr.append(int(input()))
    arr.sort()
    tmp = []
    print(arr[0])
    for i in range(3, T+1):
        n = int(input())
        if len(arr) <= i // 2:
            if arr[0] <= n:
                heapq.heappush(arr, n)
            else:
                heapq.heappush(tmp, -n)
                heapq.heappush(arr, -heapq.heappop(tmp))
        else:
            if arr[0] < n:
                heapq.heappush(arr, n)
                heapq.heappush(tmp, -heapq.heappop(arr))
            else:
                heapq.heappush(tmp, -n)
        print(arr[0])