[python/백준] 1655번: 가운데를 말해요

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

1655번: 가운데를 말해요

 

 

⭐ 문제

 

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

 

 

 

⭐ 코드 분석

 

- 두개의 heap 필요

 

1.  left heap : 최대 heap

2. right heap : 최소 heap

➡ 왼쪽 힙의 첫번째 요소는 항상 중앙값이 된다 

 

1. 왼쪽 힙과 오른쪽 힙의 길이가 같으면 (요소 * -1) 을 왼쪽 힙에 삽입한다.
     1-1. 그렇지 않으면 오른쪽 힙에 삽입한다.
2. 왼쪽 힙과 오른쪽 힙에 요소가 존재하고, 왼쪽 힙의 (첫번째 요소* -1) 가 오른쪽 첫번째 요소보다 클 때
     2-1. 왼쪽 힙의 첫번째 요소와 오른쪽 힙의 첫번째 요소를 바꿔준다. ( -1을 곱해준 뒤 바꿔준다. )
3. 왼쪽 힙의 (첫번째 요소 * -1)를 출력한다.

 

 

ex) [1, 5, 2, 10, -99, 7, 5]
num = 1 👉🏻 left = [-1] / right = []
num = 5 👉🏻 left = [-1], right = [5]
num = 2 👉🏻 left = [-2,-1], right = [5]
num = 10 👉🏻 left = [-2,-1], right = [5,10]
num = -99 👉🏻 left = [-2,-1,99], right = [5,10]
num = 7 👉🏻 left = [-2,-1,99], right = [5,7,10]
num = 5 👉🏻 left = [-5,-2,-1,99], right = [5,7,10]

 

 

 

# 파이썬 코드 작성시 input()은 시간 초과 발생하므로 sys.stdin.readline() 이용 필수 

 

 

 

 

 

⭐ 코드

 

 

import sys
import heapq
input = sys.stdin.readline

n = int(input())
max_h, min_h = [], []

for i in range(n):
    num = int(input())
    if len(max_h) == len(min_h):
        heapq.heappush(max_h, -num)
    else:
        heapq.heappush(min_h, num)

    if len(max_h) >= 1 and len(min_h) >= 1 and max_h[0] * -1 > min_h[0]:
        max_value = heapq.heappop(max_h) * -1
        min_value = heapq.heappop(min_h)
        
        heapq.heappush(max_h, min_value * -1)
        heapq.heappush(min_h, max_value)

    print(max_h[0] * -1)

 

 

 

 

https://velog.io/@uoayop/BOJ-1655-%EA%B0%80%EC%9A%B4%EB%8D%B0%EB%A5%BC-%EB%A7%90%ED%95%B4%EC%9A%94Python

[ BOJ 1655 ] 가운데를 말해요(Python)