[백준 알고리즘] 1655 문제 풀이

문제

수빈이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다.
수빈이가 정수를 하나씩 외칠때마다 동생은 지금까지 수빈이가 말한 수 중에서 중간값을 말해야 한다.
만약, 그동안 수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.
예를 들어 수빈이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면,
동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 수빈이가 외치는 수가 주어졌을 때,
동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

정답

import heapq

left = list()  # 최대힙
right = list()  # 최소힙

total_count = int(input())

for x in range(total_count):
    subin_say = int(input())

    # Step1
    if x % 2 == 0:  # 홀수 이면
        heapq.heappush(left, (-subin_say, subin_say))
    else:
        heapq.heappush(right, (subin_say, subin_say))

    # Step2
    if right and left[0][1] > right[0][1]:
        left_value = heapq.heappop(left)[1]
        right_value = heapq.heappop(right)[1]
        heapq.heappush(right, (left_value, left_value))
        heapq.heappush(left, (-right_value, right_value))

    # 중간값 출력
    print(left[0][1])

해설

해당 문제는 최대힙, 최소힙을 사용하여 구현해야 한다.
Step1에서는 순서대로 홀수번째이면 왼쪽 리스트인 최대힙에, 짝수번째이면 오른쪽 리스트인 최소힙에 넣는다.
python에서 heapq 라이브러리는 기본적으로 최소힙으로 작동하며 최대힙을 구현하기 위해서는 데이터에 -를 입력하여 최대힙을 구현한다.
Step2에서 왼쪽의 최대힙이 오른쪽 최소힙보다 크면 둘을 스위치해준다.
마지막으로 최대힙에서 제일 큰 값을 출력하면 입력받은 값의 중간 값을 구할 수 있다.