[規格]2696:中心値の検索
2687 ワード
お尻
中心値を求める
真ん中を言う
私は過去にこの問題を解決したことがあるが,方法は同じだ.
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])
Reference
この問題について([規格]2696:中心値の検索), 我々は、より多くの情報をここで見つけました
https://velog.io/@jinii/백준-2696-중앙값-찾기
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
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])
Reference
この問題について([規格]2696:中心値の検索), 我々は、より多くの情報をここで見つけました https://velog.io/@jinii/백준-2696-중앙값-찾기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol