[Python/Gold2/2696] 중앙값 구하기

|    문제

어떤 수열을 읽고, 홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성하시오.

예를 들어, 수열이 1, 5, 4, 3, 2 이면, 홀수번째 수는 1번째 수, 3번째 수, 5번째 수이고, 1번째 수를 읽었을 때 중앙값은 1, 3번째 수를 읽었을 때는 4, 5번째 수를 읽었을 때는 3이다.

|    입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주어진다. 원소는 한 줄에 10개씩 나누어져있고, 32비트 부호있는 정수이다.

|    출력

각 테스트 케이스에 대해 첫째 줄에 출력하는 중앙값의 개수를 출력하고, 둘째 줄에는 홀수 번째 수를 읽을 때 마다 구한 중앙값을 차례대로 공백으로 구분하여 출력한다. 이때, 한 줄에 10개씩 출력해야 한다.

 

---

정답 코드

import sys, heapq
input = sys.stdin.readline

class Solution:
    def mid_value(self):
        T = int(input())
        for _ in range(T):
            m = int(input()) # 수열의 크기
            arr = []
            for _ in range(m//10 + 1):
                a = list(map(int, input().split()))
                arr.extend(a)
            less = []
            more = []
            res = []
            res.append(arr[0])
            mid = arr[0]
            for idx, v in enumerate(arr[1:], 1):
                if v < mid:
                    heapq.heappush(less, -v)
                else:
                    heapq.heappush(more, v)
                
                if idx % 2 == 0:
                    if len(less) > len(more):
                        heapq.heappush(more, mid)
                        mid = -heapq.heappop(less)
                    elif len(less) < len(more):
                        heapq.heappush(less, -mid)
                        mid = heapq.heappop(more)

                    res.append(mid)
            print(len(res))
            for i in range(0, len(res), 10):
                print(*res[i:min(len(res), i+10)])
if __name__ == "__main__":
    s = Solution()
    s.mid_value()

 

 

|    비고

가운데를 말해요 상위버전. 사실 핵심적인 부분은 같다. mid값 기준 작은 값들은 less배열에, mid값 기준 큰 값들은 more배열에 넣고 값을 비교하여 중앙값을 새로 지정해주면 된다.