[規格]2696:中心値の検索


お尻


中心値を求める

真ん中を言う
私は過去にこの問題を解決したことがあるが,方法は同じだ.
2つのお尻を作成します.左はMaxお尻、右はMin Hipです.左のリストが常に右のリストより小さい場合は、
左のお尻の最初の値は中間値でしょうか?
これは論理で、2番目の繰り返し文でループすると中間値が出力されます.
各行に10文字の入力と出力が必要であるため、nは10文字未満と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])