|
import sys
input = sys.stdin.readline
import heapq
testcase = int(input())
for j in range(testcase) :
n = int(input())
l = []
if n % 10 == 0 :
for i in range(n // 10) :
l = l + list(map(int, input().split()))
else :
for i in range(n // 10 + 1) :
l = l + list(map(int, input().split()))
under = []
over = []
ans = []
for i in range(n) :
x = l[i]
if len(under) == len(over) :
heapq.heappush(under, -x)
else :
heapq.heappush(over, x)
if over != [] and -under[0] > over[0] :
a = -heapq.heappop(under)
b = heapq.heappop(over)
heapq.heappush(under, -b)
heapq.heappush(over, a)
if len(under) > len(over) :
ans.append(-under[0])
s = len(ans)
print(s)
for i in range(s // 10) :
for k in range(9) :
print(ans[10 * i + k], end = ' ')
print(ans[10 * i + 9])
for k in range(s % 10 - 1) :
print(ans[s - s % 10 + k], end = ' ')
print(ans[s-1])
|
1655 가운데를 말해요의 코드(https://uneducatedjungler.tistory.com/41)를 거의 그대로 쓰되
중앙값을 출력하는 타이밍이 다르고 출력 포맷이 까다로우니 잘 지켜줘야 한다.
문제를 풀어볼수록 기존에 풀어본 문제와 상황은 다르지만 위상적으로 같은(?) 문제가 등장하는 것 같다.
'Week 01 ~ 04 : 알고리즘 문제 풀이' 카테고리의 다른 글
| 파이썬 백준 2749 피보나치 수 3 (0) | 2021.11.17 |
|---|---|
| 파이썬 백준 12846 무서운 아르바이트 (0) | 2021.11.17 |
| 파이썬 백준 11286 절댓값 힙 (0) | 2021.11.17 |
| 파이썬 백준 1927 최소 힙 (0) | 2021.11.17 |
| 파이썬 백준 14003 가장 긴 증가하는 부분 수열 5 (0) | 2021.11.17 |