[BOJ 1655 / 파이썬] 가운데를 말해요

0. 문제 링크

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

1655번: 가운데를 말해요

1. 문제

2. 해결 알고리즘

우선순위 큐

3. 이 문제의 특징

중간 값을 어떻게 보관하고 얻어 낼지가 관건인 문제 같다.

중간 값 보다 작은 수를 우선 순위 큐(작은 힙)에 저장하고 중간보다 큰 수를 다른 우선 순위 큐(큰 힙)에 저장하는 것이다.

코드는 다음과 같다.

import sys
import heapq

input = sys.stdin.readline


def main():
	N = int(input())
	
	right, left = [], []
	
	now = int(input())
	print(now)
	
	for i in range(1, N):
		temp = int(input())
		if len(right) == len(left):
			if now > temp:
				heapq.heappush(right, now)
				heapq.heappush(left, -temp)
			else:
				heapq.heappush(right, temp)
				heapq.heappush(left, -now)
			now = -heapq.heappop(left)
		else:
			if now > temp:
				heapq.heappush(left, -temp)
			else:
				heapq.heappush(left, -now)
				heapq.heappush(right, temp)
				now = heapq.heappop(right)
		print(now)


main()

여기서 핵심은 두 가지 인것 같다.

1. 작은 힙에서 pop을 할 때 작은 힙에서 가장 큰 수가 나와야 한다.

여기서 핵심은 작은 힙에 push 할 때 -를 붙여서 넣는 것이다.

그러면 가장 큰 수는 가장 작은 수로 변하여서 힙에 들어가기 때문이다.

2. 새로 입력된 숫자와 중간 값 비교후 처리가 중요하다.

중간 값이라는 것은 작은 힙과 큰 힙의 크기가 비슷해야 한다. 새로 입력된 숫자와 중간 값을 비교해서 작은 힙의 크기와 큰 힙의 크기가 

+-1 차이 혹은 동등하게 항상 유지가 되어야 한다.

4. 이 문제를 풀면서 알게 된 점

파이썬에는 우선순위 큐 라이브러리가 있다.

또한 위 코드 처럼 heapq를 통해서 우선순위 큐를 구현할 수 있다.

하지만 우선순위 큐가 항상 최적의 시간으로 실행되는 것 같지는 않다.

간단하게 테스트 한 결과는 다음과 같다.

확실히 우선순위 큐가 더 느림을 확인 할 수 있다.

위 문제도 PriorityQueue 라이브러리를 사용할 경우 시간 초과가 뜸을 알 수 있었다.

이제 우선순위 큐는 Heapq를 써야 할 것 같다.