[Python - heapq] 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줄에 걸쳐 백준이의 동생이 말해야 하는 수를 순서대로 출력한다.

📌 문제 풀이

👨‍🏫 접근

힙을 사용해서 푸는 문제. 이미 우선순위 큐를 사용해서 풀어야 하는 문제라고 해서 접근할 수 있었는데, 몰랐으면 접근이 굉장히 어려웠을 것 같다. 우선순위 큐로 작은 수와 큰 수로 나누어서 문제를 풀이해준다. 그리고, 짝수에서는 더 작은 것을 출력할 수 있기 때문에 작은 수를 담는 리스트에서 계속해서 수를 뽑아내도록 한다.

 

작은 수를 담는 배열은 최대 힙을 사용하고, 큰 수를 담는 배열은 최소 힙을 사용하도록 한다. 작은 수들을 담은 리스트에서는 가장 큰 값을 출력해야 가운데에 가까워지기 때문이다. 비슷한 이유로 큰 수를 담는 배열은 가장 작은 갑을 출력해야 가운데에 가까워진다.

👨‍🏫 문제 풀이

📄 전체 코드

import sys
import heapq
input = sys.stdin.readline

n = int(input())

left, right = [], []

for _ in range(n):
    k = int(input())

    if len(left) == len(right):
        heapq.heappush(left, (-k, k))  # 좌측은 최대 힙이 필요
    else:
        heapq.heappush(right, (k, k))  # 우측은 최소 힙이 필요, 간단한 출력을 위해 입력 양식 통일

    if right and left[0][1] > right[0][1]:
        MIN = heapq.heappop(right)[1]
        MAX = heapq.heappop(left)[1]
        heapq.heappush(left, (-MIN, MIN))
        heapq.heappush(right, (MAX, MAX))

    print(left[0][1])

📄 준비

import sys
import heapq
input = sys.stdin.readline

n = int(input())

left, right = [], []

좌측과 우측으로 두 개의 배열을 만들어주었다. 이렇게 해서 조건에 따라서 좌 우로 값을 분류한다.

📄 풀이

for _ in range(n):
    k = int(input())

    if len(left) == len(right):
        heapq.heappush(left, (-k, k))  # 좌측은 최대 힙이 필요
    else:
        heapq.heappush(right, (k, k))  # 우측은 최소 힙이 필요, 간단한 출력을 위해 입력 양식 통일

    if right and left[0][1] > right[0][1]:
        MIN = heapq.heappop(right)[1]
        MAX = heapq.heappop(left)[1]
        heapq.heappush(left, (-MIN, MIN))
        heapq.heappush(right, (MAX, MAX))

    print(left[0][1])

두 개의 길이가 같은 상황에서는 왼쪽에 값을 보낸다. 그 이유는 우리는 항상 좌측에서 값을 뽑아낼 것이기 때문이다. 만약 짝수일 때 더 큰 값을 출력하라고 했으면, 오른쪽에 값을 보냈을 것이다.

 

그 후에 만약 좌측에서 가장 큰 값이 우측에서 가장 작은 값보다 크다면 그 값은 가운데 값이 아니라 더 큰 값이다. 그렇기 때문에 서로 값을 스와이프 해준다. 힙으로 매번 값을 넣었기 때문에 0번 인덱스를 사용하면 가장 큰 값이나 가장 작은 값을 얻어낼 수 있다.

📌 총평

힙 문제는 쉬운 문제들이었는데 확실히 자료구조를 생각해내서 문제를 풀라고 하니까 난이도가 급상승한다...