[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])