[Algorithm] 백준 1655 - 가운데를 말해요 in Python(파이썬)

💡 백준 1655:

큐 기본 구조 활용 및 우선순위큐 이해

🌱 코드 in Python

알고리즘: Queue

처음 생각은 배열을 계속 크기순으로 유지하려고 하는 것이었으나,
당연히 시간초과가 날게 뻔했다

그래서 두번째로 접근한 생각은 두부분으로 나눠서 중간값을 찾자! 였다
상대적으로 작은 수들과 상대적으로 큰 수들을 양분한 뒤, 작은 쪽에서 가장 큰 값 혹은 큰 쪽에서 가장 작은 값이 중간값이 되게끔 말이다

더하여 문제에서 짝수개에서는 더 작은 수를 결과값으로 하라고 하기 때문에
결국 작은 수에서 가장 큰 값을 찾는 것에 집중하면 되는 문제였다

import sys, heapq

input = sys.stdin.readline
n = int(input())
left = []
right = []
for i in range(n):
	num = int(input())
	if len(left) == len(right): # 둘의 길이가 똑같을 땐 왼쪽에 넣기
		heapq.heappush(left, -num) # 첫 ~ 중간값인 왼쪽은 max_heap 구조
	else: # 둘의 길이가 다를 땐 (=왼쪽이 클 때) 오른쪽에 넣기
		heapq.heappush(right, num) # 중간값 ~ 끝인 오른쪽은 max_heap 구조
	if right and -left[0] > right[0]: # 넣고 난 후 오른쪽이 존재할 경우 왼쪽에서 가장 큰 경우와 오른쪽에서 가장 작은 경우를 비교하여 왼쪽이 더 클 경우
		heapq.heappush(left, -heapq.heappop(right)) # 두 수를 swap
		heapq.heappush(right, -heapq.heappop(left))
	print(-left[0])	# 왼쪽에서 가장 큰 값 = 중간값 출력

먼저 두개의 heap 배열을 만드는데, 가장 작은 원소 ~ 중간값까지는 왼쪽 배열에 중간값 ~ 가장 큰 원소는 오른쪽 배열에 넣는다
일단 첫 원소가 들어오면 왼쪽에 때려넣어야 하기 때문에 길이가 같을 때 일단 먼저 왼쪽에 넣는다
왼쪽에 넣으면 오른쪽이 작아지게 되고 이때 오른쪽에 넣는다
그러면 배열의 길이는 1) 왼쪽 == 오른쪽, 2) 왼쪽 > 오른쪽 이 두 경우밖에 생기지 않는다

배열의 원소를 일단 집어넣은 뒤 넣을 때마다 왼쪽에서 가장 큰 값과 오른쪽에서 가장 작은 값만 서로 비교하여 주고받고 하다보면
자연스럽게 왼쪽에는 작은 값들, 오른쪽에는 큰 값들이 들어가게 된다

🧠 기억하자

1. 내가 무엇을 찾아야 하는지 잘, 잘 파악하자!

백준 1655 바로가기