[🥇2 / 백준 1655 / 파이썬] 가운데를 말해요

 

1655번: 가운데를 말해요

문제

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

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

입력

첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.

출력

한 줄에 하나씩 N줄에 걸쳐 수빈이의 동생이 말해야하는 수를 순서대로 출력한다.

 

예제 입력  7 1 5 2 10 -99 7 5

예제 출력  1 1 2 2 2 2 5

 

풀이

 

현재까지 입력받은 수들의 중앙값을 계속하여 출력하는 문제이다.

 

중앙값을 찾는 방법을 생각해 보자.

 

 

위와 같이 정렬된 배열이 있다면, 단순히 배열의 길이를 2로 나눈 몫을 인덱스로 출력하면 될 것이다.

 

하지만 문제에서는 약 100,000개의 수를 랜덤으로 입력받기 때문에

그때마다 정렬을 시도한다면 O(n^2)이 되어 문제를 제 시간에 풀 수 없을 것이다.

 

따라서 수를 입력받을 때마다 손쉽게 정렬할 수 있는 우선순위 큐를 이용하여 문제를 풀어야 한다.

위 행렬을 2개로 구분하여 보기로 하자.

 

 

편의상 최대 힙의 배열 순서는 뒤집지 않고, 각각 정렬된 1차원 배열로 가정하겠다.

각 부분을 최대 힙과 최소 힙으로 나눔으로써 최대 힙의 뿌리 노드를 출력하면 중앙값을 구할 수 있게 된다.

 

수가 랜덤으로 들어오기 때문에 숫자들을 어느 힙에 둘지 생각해야 한다.

우선 중앙값을 기준으로 이보다 더 큰 것은 무조건 최소 힙, 작은 것은 최대 힙에 두기로 하자.

 

그리고 힙에 숫자를 push했을 때 2가지 경우로 나누자.

 

 

1. 최소 힙의 길이가 최대 힙 보다 길어질 때

 

 

최대 힙의 뿌리 노드를 출력해야 하므로 최소 힙의 길이가 최대 힙보다 길어진다면 이미 중앙값이 될 수 없다.

최소 힙의 뿌리 노드만 pop해서 최대 힙으로 넘겨준다면 자연스럽게 문제가 풀리게 된다.

 

만약 7이 없는 상태, 즉 최대 힙과 최소 힙의 길이가 같은 경우에는

문제에서 수의 개수가 짝수일 경우 더 작은 것을 출력하라 했으므로 따로 연산이 필요하지 않다.

 

 

2. 최대 힙의 길이가 최소 힙보다 2개 만큼 길어질 때

 

 

최대 힙이 최소 힙보다 너무 길어졌다.

중앙값을 벗어나게 되었으므로 이번에는 최대 힙의 뿌리노드를 pop해서 최소 힙으로 넘겨주면 된다.

 

 

이제 이것을 이번에는 heapq 모듈을 사용하여 풀었다.

heapq는 배열에 수를 집어넣을 때 손쉽게 최소 힙을 구성할 수 있게 해주는 모듈이다.

 

단, 최대 힙은 지원하지 않기 때문에 두 가지 요령을 사용하여 만들 수 있다.

 

첫째는 입력받은 수를 뒤집은 것과 안 뒤집은 것으로 튜플로 구성해주고,

pop이 필요할 땐 뒤집어서 튜플의 두 번째 것을 출력하면 된다.

 

두번째는 헷갈리지 않을 자신이 있다면 단순히 부호를 뒤집어서 배열을 구성하면 된다.

물론 pop을 하거나 대소 비교를 할 때에는 꼭 부호를 뒤집어서 해야 할 것이다.

 

두 방법 중 자신에게 더 편한 방법으로 모듈을 사용하면 되겠다.

 

 

첫 번째 요령 사용

import sys, heapq
input = sys.stdin.readline
n = int(input())

# 첫 번째 숫자는 직접 넣어주었다.
num = int(input())
print(num)
minHeap, maxHeap = [],[(-num,num)]

for i in range(n-1):
    num = int(input())
    if num > maxHeap[0][1]:
        heapq.heappush(minHeap, num)
    else:
        heapq.heappush(maxHeap, (-num,num))
        
    if len(minHeap) > len(maxHeap):
        temp = heapq.heappop(minHeap)
        heapq.heappush(maxHeap, (-temp,temp))
    elif len(minHeap)+1 < len(maxHeap):
        heapq.heappush(minHeap, heapq.heappop(maxHeap)[1])
    print(maxHeap[0][1])

 

 

두 번째 요령 사용

import sys, heapq
input = sys.stdin.readline
n = int(input())

num = int(input())
print(num)
minHeap, maxHeap = [],[-num]

for i in range(n-1):
    num = int(input())
    if num > -maxHeap[0]:
        heapq.heappush(minHeap, num)
    else:
        heapq.heappush(maxHeap, -num)
        
    if len(minHeap) > len(maxHeap):
        temp = heapq.heappop(minHeap)
        heapq.heappush(maxHeap, -temp)
    elif len(minHeap)+1 < len(maxHeap):
        heapq.heappush(minHeap, -heapq.heappop(maxHeap))
    print(-maxHeap[0])