힙

중앙값 구하기

가운데를 말해요
과거에 이 문제를 풀었었는데, 접근 방식이 같습니다.
두개의 힙을 만들고 왼쪽은 맥스힙 오른쪽은 민힙으로 하고 왼쪽 리스트가 항상 오른쪽 리스트보다 작으면
왼쪽 힙의 첫번째 값이 중간값이 되겠지요?
그리고 홀수번째 반복문을 돈다면 가운데 값을 출력해주는 로직입니다.
한줄에 10개씩 입력, 출력해야하기 때문에 n이 10 이하인것과 초과인것으로 나누었습니다.
자세한 것은 코드로 설명하겠습니다.

import sys
import heapq
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
    	# n이 10 이하일 때 
	if n <= 10:
		lst = list(map(int, input().split()))
		left = []
		right = []
		answer = []
		for i in range(len(lst)):
			#maxHeap 갯수가 같으면 왼쪽 리스트에 넣고 맥스힙
			if len(left) == len(right):
				heapq.heappush(left, -lst[i])
			#minHeap 다르면 오른쪽 리스트에 넣고 민힙
			else:
				heapq.heappush(right, lst[i])
            		# 왼쪽 리스트가 오른쪽 리스트보다 항상 작도록 , -> 왼쪽 가장 큰 값이 오른쪽 가장 작은 값보다 크다면 두개 빼서 다시 정렬 
			if right and -left[0] > right[0]:
				lf = heapq.heappop(left)
				rg = heapq.heappop(right)
				heapq.heappush(left, -rg)
				heapq.heappush(right, -lf)
                	#  홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 추가
			if i % 2 == 0:
				answer.append(-left[0])
         	# 중앙값의 개수와 리스트 출력
		print(n // 2+1)
		print(*answer)
	else:
		left = []
		right = []
		answer = []
		lst = [[0]*10 for _ in range(n // 10+1)]
        	# row 와 column 설정 
		row = n // 10
		col = n % 10
		for i in range(row + 1):
			lst[i] = list(map(int, input().split()))
		for i in range(row+1):
        		# 맨 마지막줄은 10개가 아닐수도 있다 
			if i == row:
				for j in range(col):
					if len(left) == len(right):
						heapq.heappush(left, -lst[i][j])
					#minHeap
					else:
						heapq.heappush(right, lst[i][j])
					if right and -left[0] > right[0]:
						lf = heapq.heappop(left)
						rg = heapq.heappop(right)
						heapq.heappush(left, -rg)
						heapq.heappush(right, -lf)
                        		# 행은 상관이 없다 직접 그려보면 알 수 있다. 열이 홀수번째라면 추가 
					if j % 2 == 0:
						answer.append(-left[0])
			else:
            			#맨 마지막 줄이 아니면 10번 돈다.
				for j in range(10):
					if len(left) == len(right):
						heapq.heappush(left, -lst[i][j])
					#minHeap
					else:
						heapq.heappush(right, lst[i][j])
					if right and -left[0] > right[0]:
						lf = heapq.heappop(left)
						rg = heapq.heappop(right)
						heapq.heappush(left, -rg)
						heapq.heappush(right, -lf)
					if j % 2 == 0:
						answer.append(-left[0])
        	# 중앙값의 개수와 리스트 출력
		print(n // 2 + 1)
		for i in range(0, len(answer), 10):
			print(*answer[i:i+10])