[백준 2024/09/11] 1655번 가운데를 말해요

1. 접근 방법

https://www.acmicpc.net/problem/1655

 

2. 문제 풀이

최소 힙과 최대 힙 2개를 이용해서 문제를 풀었다. ( 조금 힌트를 얻긴 했다.. *^^* )

 

블록이 홀수 개 일 땐, 최소 힙에 블록을 넣고, 최솟값을 pop 해 최대 힙에 옮긴다. 이후, 최대 힙에서 peek를 출력하여 준다.

블록이 짝수 개 일 땐, 최소 힙에 블록을 넣고, 최솟값을 pop해 최대 힙에 옮긴다. 이후 최대 힙에서 최대를 pop하여, 최소 힙에 넣어준다.

이후, 최대힙에서 peek를 출력하여 준다.

 

아래 그림으로 더 자세히 설명해 보겠다.

 

3. 코드

import sys
import heapq
min_heap = []
max_heap = []


def find_median(i, n):
    global min_heap
    global max_heap

    if i % 2 == 1:
        heapq.heappush(min_heap, n)
        heapq.heappush(max_heap, -1 * heapq.heappop(min_heap))
        return max_heap[0] * -1

    else:
        heapq.heappush(min_heap, n)
        heapq.heappush(max_heap, -1 * heapq.heappop(min_heap))
        heapq.heappush(min_heap, -1 * heapq.heappop(max_heap))
        return max_heap[0] * -1


if __name__ == "__main__":
    for i in range(1, int(sys.stdin.readline())+1, 1):
        print(find_median(i, int(sys.stdin.readline())))