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

문제 설명

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

1655번: 가운데를 말해요

백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

---

풀이 과정

이 문제는 정렬로 풀면 시간초과 오류가 나기 때문에 우선순위 큐를 이용하여야 한다.

 

전체적인 접근 방식은

문제에서 구하고자 하는 값이 중간값이기 때문에

중간값보다 작은 값들은 leftHeap에, 큰 값은 rightHeap에 저장하는 방식이다.

 

풀이 과정은 다음과 같다.

① 중간값이라는 것은 주어진 N개의 수 중 중간에 위치한 값이기 때문에

값을 leftHeap과 rightHeap에 번갈아 넣어줌으로써 두 힙의 균형(개수)을 유지하도록 하여

leftHeap에서 pop을 했을 때 바로 중간값을 구할 수 있도록 한다.

 

② leftHeap은 최대힙으로, rightHeap은 최소힙으로 구성을 함으로써

leftHeap의 첫 원소를 중간값으로 만들 수 있다.

 

③ 이 때, rightHeap에 원소를 넣는 차례에 leftHeap보다 작은 값을 넣게 된다면

rightHeap에 중간값보다 큰 원소가 들어가게 되므로

leftHeap의 첫 원소와 rightHeap의 첫 원소를 교체하여 균형을 유지할 수 있도록 한다.

 

여기서,파이썬 코드 작성 시 주의해야 할 점은 입력 시 input()을 이용한다면 시간초과 오류가 발생하므로

sys.stdin.readline()을 이용하도록 하자.

import heapq
import sys

n = int(sys.stdin.readline())

leftHeap = []
rightHeap = []
for i in range(n):
    num = int(sys.stdin.readline())

    if len(leftHeap) == len(rightHeap):
        heapq.heappush(leftHeap, -num)
    else:
        heapq.heappush(rightHeap, num)

    if rightHeap and rightHeap[0] < -leftHeap[0]:
        leftValue = heapq.heappop(leftHeap)
        rightValue = heapq.heappop(rightHeap)

        heapq.heappush(leftHeap, -rightValue)
        heapq.heappush(rightHeap, -leftValue)

    print(-leftHeap[0])

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !