[Python] 백준 1655. 가운데를 말해요

https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

접근 방법이 백준 키로거 문제와 흡사하다.

 

[Python] 백준 5397. 키로거

키로거에서는 왼쪽 / 오른쪽 커서값을 각각 stack 자료구로에 저장했다면,

여기서는 중앙값 기준으로 큰 값은 오른쪽, 작은 값은 왼쪽에 저장한다.

 

왼쪽 값은 max_heap로, 오른쪽 값은 min_heap로 구성하고, 중앙값은 항상 max_heap의 맨 첫번째 값이 되도록 구성한다.

 

1. 왼쪽과 오른쪽 원소의 길이가 같으면, 왼쪽에 새 값을 저장한다.

2. 만약 오른쪽 heap의 값보다 왼쪽 heap의 값이 더 크면, 오른쪽과 왼쪽의 원소값을 바꿔준다.

 

 

	import heapq
	import sys
	# 중앙값 기준으로 작은 값 = left, 큰 값 = right
	left, right = [], []
	n = int(sys.stdin.readline())
	for _ in range(n):
	num = int(sys.stdin.readline())
	if len(left) == len(right):
	# max_heap.
	heapq.heappush(left, (-num, num))
	else:
	# min_heap.
	heapq.heappush(right, (num, num))
	# 오른쪽 값에 원소가 있으면서,
	# 왼쪽 값이 오른쪽 값보다 큰 경우... left원소보다 right원소가 더 커야 하는 조건에 위배
	if right and left[0][1] > right[0][1]:
	left_value = heapq.heappop(left)[1]
	right_value = heapq.heappop(right)[1]
	heapq.heappush(right, (left_value, left_value))
	heapq.heappush(left, (-right_value, right_value))
	print(left[0][1])

view raw [백준] 가운데를 말해요.py hosted with ❤ by GitHub