[Python] [BOJ] 가운데를 말해요(1655)

💡 문제 해결

1. 저장 리스트를 반으로 잘라 왼쪽, 오른쪽으로 나눈다고 생각
2. 왼쪽이라 생각할 heap리스트는 최대힙, 오른쪽은 최소힙으로 생성하여 중앙값에 접근
3. 만약 시작값이 거나, 두 리스트의 길이가 같다면 왼쪽 리스트에 저장
4. 값이 존재하는데 두 리스트의 길이가 다르다면 오른쪽 리스트에 저장
5. 두 리스트가 모두 존재하고, 중앙값이 왼쪽리스트에 들어간 값이 더 크다면 두 값을 교환
6. 위치 할당이 모두 끝난 후 왼쪽 리스트의 가장 첫번째 값이 중앙값

🧾 문제 설명

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

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

문제보기

🖨 입출력

📝 풀이

import sys, heapq

input = sys.stdin.readline

N = int(input())
nums = list(int(input()) for _ in range(N))

low_heap, high_heap = [], []
for num in nums:
    if low_heap or high_heap:
        if len(low_heap) == len(high_heap):
            heapq.heappush(low_heap, -num)
        else:
            heapq.heappush(high_heap, num)

        if low_heap and high_heap and -low_heap[0] > high_heap[0]:
            low, high = heapq.heappop(low_heap), heapq.heappop(high_heap)
            heapq.heappush(low_heap, -high)
            heapq.heappush(high_heap, -low)

    else:
        heapq.heappush(low_heap, -num)

    print(-low_heap[0])

• 출처: BAEKJOON Online Judge
• 링크: https://www.acmicpc.net/problem/1655