[BOJ] 1655. 가운데를 말해요

Python3

문제

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

키워드

• 자료구조
• 우선순위 큐

문제 풀이

문제 요구사항

백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수 개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.
백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램

변수 및 함수 설명

N: 정수의 개수(1 <= N <= 100,000)
num: 백준이가 외치는 정수 (-10,000 <= num <= 10,000)

left : 작은 값들이 담기는 heap
right : 큰 값들이 담기는 heap
answer : left heap의 루트값

풀이

우선순위 큐

우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.
우선순위 큐는 힙(heap)이라는 자료 구조를 통해 구현할 수 있다.

힙

완전 이진 트리(Complete Binary Tree)로, 부모 노드의 값이 항상 자식 노드들의 값보다 크거나(Max Heap), 작아야(Min Heap) 한다.

• push

heapq.heappush(heap, item)

• pop

heapq.heappop(heap)

문제를 풀기 위해서는 두 개의 힙이 필요하다.

• LeftHeap : 중간값보다 작은 수가 들어가는 힙
• RightHeap : 중간값보다 큰 수가 들어가는 힙

중간값도 Heap에 들어가야 하긴 하다.
문제의 조건에 따르면,

백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

라는 부분에서 중간값이 LeftHeap에 들어가야 한다는 것을 알 수 있다.
=> 즉, LeftHeap의 루트가 중간값이 된다!

최종 코드

import heapq
import sys

n = int(sys.stdin.readline())

left, right = [], []
answer = []

for _ in range(n):
    num = int(sys.stdin.readline())

    if len(left) == len(right):
        heapq.heappush(left, (-num, num))
    else:
        heapq.heappush(right, (num, num))

    if right and left[0][1] > right[0][0]:
        min = heapq.heappop(right)[0]
        max = heapq.heappop(left)[1]
        heapq.heappush(left, (-min, min))
        heapq.heappush(right, (max, max))
    
    answer.append(left[0][1])

for i in answer:
    print(i)

피드백

하아ㅏㅇ.. 다 썼는데 날라가서 다시 썼다....