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

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

1655번: 가운데를 말해요

어린이에겐 매우 어려운 게임이다. 시간제한이 0.1초 인걸 보니 기존 정렬 방식으로는 해결이 힘들 거 같다.

사실문제 풀기 전에 우선순위 큐 문제 인걸 알고 있어서 이걸 어떻게 적용할지 생각하면 되는 문제다.

 

우선순위 큐 문제는 내가 정한 우선순위가 높은 데이터가 가장 먼저 pop 되는 큐다.

근데 예제 출력 부분을 보면 1 1 2 2 같이 중복된 값이 여러 번 출력된다.

따라서 단순히 pop을 하는 건 아니라고 생각. 중간을 의미하는 값을 찾기 힘들어 큐를 두 개 쓰는 방식으로 생각했다.

 

풀이 과정

예를 들어 1 2 4 5 6 9 같이 오름차순으로 정렬된 배열을 보면, 중간값은 4이다.

여기서 배열을 절반으로 나누면 1 2 4 / 5 6 9 가 된다.

여기서 4는 왼쪽 부분에서 제일 큰 값이고, 5는 오른쪽 부분에서 제일 작은 값이다.

 

따라서 왼쪽 리스트에서 큰 값은 전체 리스트에서 중간값을 의미한다.

이것을 자료구조에 적용하면 왼쪽 부분은 최대 힙, 오른쪽 부분은 최소 힙을 사용해주면 된다.

 

데이터 입력은 왼쪽부터 번갈아 가며 힙에 추가해주면 된다.

이때 주의할 점을 입력 후 왼쪽 부분의 최댓값이 오른쪽 부분의 최솟값보다 크면 두 값을 교환해주어야 한다.

 

예를 들어 [1, 3, 6] / [8, 9]에서 4를 추가하면 [1, 3, 6] / [4, 8, 9]가 된다.

여기서 6과 4를 교환해주면 [1, 3, 4] / [6, 8, 9] 이렇게 왼쪽 부분에서 계속 중간값을 출력할 수 있다.

 

전체 코드

import heapq
import sys

max_heap = []
min_heap = []
input = sys.stdin.readline
N = int(input().rstrip())

for i in range(N):
    x = int(input().rstrip())
    if i % 2 == 0:
        heapq.heappush(max_heap,-x)
    else:
        heapq.heappush(min_heap,x)

    if max_heap and min_heap and -max_heap[0] > min_heap[0]:
        maxh_value = -heapq.heappop(max_heap)
        minh_value = heapq.heappop(min_heap)

        heapq.heappush(max_heap,-minh_value)
        heapq.heappush(min_heap,maxh_value)

    print(-max_heap[0])

 파이썬에 있는 heapq라이브러리로 만든 힙은 기본적으로 최소 힙이다.

따라서 push 할 때 값을 음수로 만들면 최대 힙으로도 사용 가능하다.

 

값을 교환할 때 최대 힙과 최소 힙에 값이 존재해야 하므로 if문에 조건을 넣어준다.