1655. 가운데를 말해요 (Python)

1655번: 가운데를 말해요

 

풀이

 가운데를 기준으로 낮은쪽을 저장하는 힙(smallerNumbers)과 높은쪽을 저장하는 힙(biggerNumbers)을 사용하여 해결하였다. smallerNumbers의 경우는 최대힙을 사용하였고 biggerNumbers의 경우는 최소힙을 사용하였다. 이는 작은 숫자들중에서는 가장 큰 숫자(smallerRep)가 가운데에 올 수 있고 큰 숫자들중에서는 가장 작은 숫자(biggerRep)가 가운데에 올 수 있기 때문이다.

 

 smallerRep와 biggerRep는 변수로 두어 따로 관리한다. 이제 숫자를 입력 받으면 다음과 같은 3가지 경우로 나누어 처리한다

 

(1) smallerRep 이하일 경우

- smallerRep 이하일 경우에는 smallerNumbers에 입력값을 넣어준다.

 

(2) smallerRep와 biggerRep 사이일 경우 

- smallerRep를 입력 받은 숫자로 바꿔주고 기존의 smallerRep값은 smallerNumbers에 넣어준다.

 

(3) biggerRep 이상일 경우

- biggerRep 이상일 경우에는 biggerNumbers에 입력값을 넣어준다.

 

 그러나 이때 한 가지 주의해야 할 것이 있다. smallerRep와 biggerRep가 전체 숫자에서 가운데에 있을 수 있으려면 smallerNumbers와 biggerNumbers에 들어있는 값의 개수의 차이가 1을 넘어서면 안된다. 예를 들어 입력값으로 (1, 2, 3, 4, 5)가 들어오면 처음 두 번에서 smaellerRep는 1이 되고 biggerRep는 2가 된다. 나머지 3, 4, 5는 biggerRep보다 크므로 biggerNumbers에만 값들이 추가되고 이렇게 되면 smaellerRep와 biggerRep는 가운데에 존재하는 숫자가 아니게 된다. 

 따라서, 값을 넣어 주고 두 힙의 원소의 개수를 비교하여 2이상 차이가 날 경우에는 두 힙의 차이를 맞춰주는 과정이 필요하다. 만약 smallerNumbers의 원소 개수가 더 많다면 다음의 과정이 진행된다.

• biggerRep를 biggerNumbers에 넣어준다.
• smallerRep를 biggerRep에 대입한다.
• smallerRep는 smallerNumbers에서 최댓값으로 설정한다. 

 위와 같은 과정을 통해서 두 힙의 원소의 개수 차이를 맞춰주고 smaellerRep와 biggerRep는 전체 숫자 중 가운데에 있는 숫자들로 유지할 수 있다.

 

 마지막 출력에서는 홀수 번째로 입력한 값의 경우에는 lowerNumbers와 higherNumbers중 더 많은 값을 가지고 있는 쪽의 대표 숫자를 출력해 주면 되고 짝수 번째로 입력한 값의 경우에는 lowerRep를 출력해 주면 된다.

 

코드

import heapq
import sys
INF = float('INF')
input = sys.stdin.readline


# 두 힙의 길이를 조정하기 위한 함수
def balance(isSmaller):
    global smallerRep, biggerRep

    if isSmaller: # 작은 쪽 숫자들이 더 많을 경우
        heapq.heappush(biggerNumbers, biggerRep) # 큰 쪽 숫자에 기존의 큰 값의 대표를 추가해주고
        biggerRep = smallerRep # 작은 값의 대표를 큰 값의 대표로 바꿔준다
        smallerRep = -heapq.heappop(smallerNumbers) # 이제 작은 값의 대표는 smallerNumbers에서 새로 갖고온다.
    else: # 큰 쪽 숫자들이 더 많을 경우
        heapq.heappush(smallerNumbers, -smallerRep) # 작은 쪽 숫자에 기존의 smallerRep를 추가해주고
        smallerRep = biggerRep # biggerRep를 smallerRep로 바꿔준다
        biggerRep = heapq.heappop(biggerNumbers) # 이제 biggerRep는 biggerNumbers에서 새로 갖고온다.


if __name__ == '__main__':
    N = int(input())
    smallerNumbers = [] # 가운데를 기준으로 작은 숫자들을 모아 놓는 힙 (최대힙)
    biggerNumbers = [] # 가운데를 기준으로 큰 숫자들을 뫃아 놓는 힙 (최소힙)
    smallerRep = INF # 작은 숫자들 중 가장 큰 숫자 (가운데에 있을 수 있는 숫자)
    biggerRep = -INF # 큰 숫자들 중 가장 작은 숫자 (가운데에 있을 수 있는 숫자)

    if N == 1:
        print(int(input()))
        sys.exit()

    for _ in range(2): # 첫 숫자 2개는 작은 숫자 출력
        number = int(input())
        smallerRep = min(smallerRep, number)
        biggerRep = max(biggerRep, number)
        print(smallerRep)

    # 두 힙에 INF를 넣는 이유는 가운데에 있을 수 있는 숫자는 xxRep 변수에 저장해두고 힙에는 넣지 않기 때문
    # 두 힙의 길이를 비교해야 하는 경우가 있어 임시로 INF를 넣는다 
    heapq.heappush(smallerNumbers, INF) 
    heapq.heappush(biggerNumbers, INF)

    for i in range(3, N+1):
        number = int(input()) # 입력 받은 숫자 

        if number <= smallerRep: # 입력 받은 숫자가 smallerRep 이하일 때, smallerNumbers에 추가
            heapq.heappush(smallerNumbers, -number)
        elif smallerRep < number < biggerRep: # 두 중간 값 사이일 경우
            heapq.heappush(smallerNumbers, -smallerRep) # 기존의 smallerRep는 smallerNumbers에 넣어주고
            smallerRep = number # smallerRep를 입력 값으로 변경
        else: # 입력 받은 숫자가 biggerRep 이상일 때
            heapq.heappush(biggerNumbers, number) # biggerNumbers에 추가 


        # 두 힙의 길이의 차이가 2 이상이 될 경우
        # smallerRep 또는 biggerRep가 가운데 숫자에서 벗어나게 되므로 조정이 필요함
        if abs(len(smallerNumbers) - len(biggerNumbers)) > 1:
            if len(smallerNumbers) > len(biggerNumbers):
                balance(isSmaller=True)
            else:
                balance(isSmaller=False)


        if i % 2 == 1: # 외친 수의 개수가 홀수일 경우, 더 많은 숫자를 갖고 있는 쪽의 대표값이 가운데 숫자가 된다
            if len(smallerNumbers) > len(biggerNumbers): 
                print(smallerRep)
            else:
                print(biggerRep)
        else: # 짝수개일 경우에는 두 숫자가 가운데 숫자가 되고 이 중 더 작은 값인 smallerRep를 출력해준다.
            print(smallerRep)