백준 1655 가운데를 말해요

//문제 요약

일련의 숫자들이 1회당 1개 주어지는 경우

매 회마다 주어졌던 숫자들의 중간값을 말하는

프로그램을 짜시오

 

//사고

 

가장 먼저 해볼 수 있는 생각은

리스트를 만들어서 2칸짜리 윈도우를 만들고

슬라이딩하면서 주어진 숫자가 두 수의 사이값인 경우 삽입하는 식으로

주어진 숫자들을 나열하고 그 배열을 중간값을 불러주면 될 것 같다.

 

하지만 그렇게 되면 최악의 경우

계속해서 배열의 가장 끝에 숫자를 더해야 하고

더하기 위해서 배열을 모두 훑어야 하므로

굉장히 비효율적인 방식이라고 할 수 있다.

 

사실 알아야하는 부분은

가운데 숫자가 무엇인가인데

계속해서 가운데에 두 숫자만 관찰할 경우

어떤 숫자들은 삽입되어도 가운데 수를 변화시키지 않으므로

그런 연산들은 생략하여 낭비하지 않을 수 있다.

 

예를 들면

[1, 5] => 1 인 숫자에

0을 추가하면

[0, 1, 5] => 1

8을 추가하면

[0, 1, 5, 8] => 1

이렇게 계속 가운데 수를 유지할 수 있다.

그래서 가운데의 두 숫자만 관찰하면서

어떤 규칙을 통해서 작은 쪽 큰 쪽으로 구분하고

나눠서 집어넣어주면 될 것 같은 생각이 들었다.

 

그런데 문제는

9를 추가하면

[0, 1, 5, 8, 9] => 5

2를 추가하면

[0, 1, 2, 5, 8, 9] => 2

4를 추가하면

[0, 1, 2, 4, 5, 8, 9] => 4

이런 식으로 계속 바뀐다는게 문제인데

 

이런 경우에까지 모두 통할 수 있는 규칙을 찾는게 어려웠다.

결국 아래의 링크를 참고하여 풀이를 진행했다.

https://yabmoons.tistory.com/478

[ 백준 1655 ] 가운데를 말해요 (C++)

 

 

//풀이

### 백준
### 1655번
### 가운데를 말해요

### 풀이 참고
# https://yabmoons.tistory.com/478

# 1. 최대 힙의 크기는 항상 최소힙의 크기보다 같거나 1만큼 크다.
# 2. 최소 힙의 모든 원소는 최대힙의 모든 원소보다 항상 크거나 같아야 한다.


import sys
from heapq import heappop, heappush

def readline():
    return int(sys.stdin.readline().strip())

N = readline()
median = []
max_pq, min_pq = [], []
for i in range(N):
    n = readline()
    
    if len(max_pq) == len(min_pq):
        heappush(max_pq, -n)
    else:
        heappush(min_pq, n)
    
    if max_pq and min_pq :
        max_pop = -heappop(max_pq)
        min_pop = heappop(min_pq)
        if max_pop > min_pop:
            heappush(max_pq, -min_pop)
            heappush(min_pq, max_pop)
        else:
            heappush(max_pq, -max_pop)
            heappush(min_pq, min_pop)

    max_pop = -heappop(max_pq)
    median.append(max_pop)
    heappush(max_pq, -max_pop)

for m in median:
    print(m)

 

가운데를 기준으로 작은 쪽 수를 모으는 힙은 최대값을 우선으로 pop 하는 힙이어야 한다.

가운데를 기준으로 큰 수를 모으는 힙은 최소값을 우선으로 pop 해야한다.

그러면 두 힙에서 pop한 수 중 작은 수가 median 값이 된다.

그런데 짝수의 수가 주어진 경우는 두 중간값 중 더 작은 값을 선출하므로

작은 수를 모으는 힙이 항상 같거나 더 많은 숫자를 가지고 있어야 한다.