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

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

1655번: 가운데를 말해요

 

문제정리 : N 개의 개수만큼의 수를 입력 받은 후, 입력 받을 때마다, 중앙값을 출력.

 

import heapq
import sys
# 항상 최소가 최대보다 1보다 크거나 같게 함으로서 크기 고정하고 입력되는 수와 최소의 최대값과 비교하며 출력
n = int(sys.stdin.readline().rstrip())
big = [] # 중앙값보다 큰 값들 (중앙값 기준 오른쪽)

small = [] # 중앙값보다 작거나 같은 값들 (중앙값 기준 왼쪽이거나 중앙)

for i in range(n):
    if i == 0: # 맨 처음 경우
        a = int(sys.stdin.readline().rstrip())
        heapq.heappush(big,a) # 오른쪽에 입력값 삽입
        print(a) # 입력값 출력 (맨처음이니 무조건 중앙값이다.)
        
    elif i == 1: # 두번째 경우
        a = int(sys.stdin.readline().rstrip())
        num = heapq.heappop(big) # 오른쪽 중 최솟값 
        if a >= num: # 입력값이 큰 경우
            print(num) # 최솟값 출력 (둘 중 작은 값이 중앙값.)
            heapq.heappush(big,a) # 오른쪽에 입력값 삽입 후
            heapq.heappush(small,-num) # 왼쪽에 최솟값 삽입(왼쪽은 나중에 최댓값을 구해야하므로 -를 곱해 삽입)
        else: # 입력값이 작은 경우
            print(a) # 입력값 출력 (둘 중 작은 값이 중앙값.)
            heapq.heappush(big,num) # 오른쪽에 최솟값 삽입 후(이전과 그대로)
            heapq.heappush(small,-a) # 왼쪽에 입력값 삽입(왼쪽은 나중에 최댓값을 구해야하므로 -를 곱해 삽입)
            
    else: # 세번째 이상의 경우 (일반화 경우)
        if (i + 1) % 2 == 1:  # 홀수번째 일 경우 무조건 최소에 넣음
            a = int(sys.stdin.readline().rstrip())
            small_max = heapq.heappop(small) # 왼쪽의 최댓값
            if a >= -small_max: # 입력값이 최댓값보다 클 때(최댓값이 중앙값)
                heapq.heappush(big, a) # 오른쪽에 입력값 삽입
                big_min = heapq.heappop(big) 
                print(big_min)
                heapq.heappush(small, -big_min)
                heapq.heappush(small, small_max)
            else: # 입력값이 최댓값보다 작을 때 (입력값이 중앙값)
                heapq.heappush(small, -a)
                print(-small_max)
                heapq.heappush(small, small_max)
        else:#짝수번째 경우 무조건 최대에 넣음
            a = int(sys.stdin.readline().rstrip())
            small_max = heapq.heappop(small)
            if a >= -small_max:
                print(-small_max)
                heapq.heappush(small, small_max)
                heapq.heappush(big,a)
            else:
                heapq.heappush(big,-small_max)
                heapq.heappush(small,-a)
                num = heapq.heappop(small)
                print(-num)
                heapq.heappush(small,num)

항상 왼쪽의 개수가 오른쪽의 개수보다 1보다 크거나 같게 함으로서 크기 고정하고 입력되는 수와 최소의 최대값과 비교하며 출력한다.

 

항상 왼쪽의 개수를 오른쪽의 개수보다 1보다 크거나 같게 하면 중앙값은 항상 왼쪽의 최댓값이다.

따라서 입력값을 받을 때 왼쪽의 최댓값과 비교하여 왼쪽에 입력값을 넣을 지, 왼쪽의 최댓값을 넣을지를 결정한다.

그후 나머지 수를 오른쪽에 넣어서 개수를 맞춘다.