[BOJ][Python] 백준 1655번: 가운데를 말해요
1일 1PS 59일차!
📚 문제
골드 2 가운데를 말해요
💡 풀이 과정
-
이전에 중간값을 구하는 문제를 풀어본 적이 있어서 이미 우선순위 큐를 이용해야하는 것을 알고 있다.
- MaxHeap 과 MinHeap 을 사용한다.
- LargeHeap 에는 받는 값들 중에서 중간값보다 큰 값을 저장하고 SmallHeap 은 중간값보다 작은 값을 저장한다.
- SmallHeap 에 먼저 수를 저장하면 홀수 번째마다 중간값은 항상 SmallHeap 에서 가장 큰 값이 된다. 이를 위해서는 MaxHeap 을 사용한다.
- 짝수 번째에서는 SmallHeap 의 가장 큰 값과 LargeHeap 의 가장 작은 값을 비교해야한다.
- 위 같은 상태를 유지하기 위해서는 Small, LargeHeap 에 각각 하나의 요소가 들어갔을 때 Small 의 가장 큰 값과 Large 의 가장 큰 값을 비교하고 필요 시 바꾸어주어야한다!
📌포인트
- 해당 문제에서는 input() 의 개수가 너무 많기에 sys.stdin.readline() 을 사용해야 시간 초과가 발생하지 않는다.
💻 코드
import heapq
import sys
N = int(input())
LargeHeap = []
SmallHeap = []
for i in range(N):
j = int(sys.stdin.readline())
if i % 2 == 0:
heapq.heappush(SmallHeap, -1 * j)
else:
heapq.heappush(LargeHeap, j)
if LargeHeap and LargeHeap[0] < -1 * SmallHeap[0]:
small = heapq.heappop(SmallHeap)
large = heapq.heappop(LargeHeap)
heapq.heappush(LargeHeap, -1 * small)
heapq.heappush(SmallHeap, -1 * large)
print(-SmallHeap[0])
댓글남기기