백준 문제풀이
백준 1655 - 가운데를 말해요 [Python]
Vermeil
2021. 3. 22. 11:40
1655번: 가운데를 말해요
첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1
www.acmicpc.net
중앙값을 기준으로 우선순위 큐 두 개를 만들어주고 풀었다.
코드 더러워지는거 싫어서
hpp = heapq.heappop
hps = heapq.heappush
라고 미리 써두고 풀었다
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
import heapq, sys
input = sys.stdin.readline
hpp = heapq.heappop
hps = heapq.heappush
l = []
r = []
n = int(input())
for i in range(n):
t = int(input())
if i < 2:
hps(r, t)
now = r[0]
print(r[0])
continue
if t <= now:
hps(l, -t)
else:
hps(r, t)
if len(l) == len(r):
lpop = hpp(l)
hps(r, -lpop)
if len(l) + 3 == len(r):
rpop = hpp(r)
hps(l, -rpop)
now = r[0]
print(r[0])
|
cs |