백준 1655번: 가운데를 말해요 (Python)

접근

기존의 힙 트리 알고리즘을 이용하여 푸는 문제였다. 최대 힙과 최소 힙 두가지 모두 써야하기 때문에 기존에 작성했던 최대 힙, 최소 힙 함수를 사용하지 않고 heapq 라이브러리를 불러와서 문제를 해결해보았다.

최대 힙 문제

2021.04.05 - [코딩/백준 (Python)] - 백준 11279번: 최대 힙 (Python)

백준 11279번: 최대 힙 (Python)

최소 힙 문제

2021.04.05 - [코딩/백준 (Python)] - 백준 1927번: 최소 힙 (Python)

백준 1927번: 최소 힙 (Python)

heapq 라이브러리는 힙 트리 중 최소 힙으로만 만들어주기 때문에 최대 힙 배열을 만들기 위해서는 추가적인 조작이 필요하다. 힙 배열에 tuple을 이용하여 (-m, m) 요소를 넣어주게 되는데, 가장 작은 값 -m이 맨 앞에 오는 최소 힙을 만듦으로써 두번째 요소로 보면 가장 큰 값 m이 맨 앞에 있는 최대 힙 배열을 만들어 줄 수 있다.

최대 힙을 가지는 왼쪽 트리와 최소 힙을 가지는 오른쪽 트리 두가지를 작성하여 왼쪽 트리의 가장 큰 값(최대 힙)이 전체 수열의 중간 값이 되도록 코드를 작성하면 문제를 해결할 수 있다.

코드

import sys
import heapq

n = int(sys.stdin.readline())
leftheap = []
rightheap = []
for _ in range(n):
    m = int(sys.stdin.readline())
    if len(leftheap) == len(rightheap):
        heapq.heappush(leftheap, (-m, m))
    else:
        heapq.heappush(rightheap, (m, m))

    # 좌우에 번갈아서 넣다보면 왼쪽 힙 최대 값보다 오른쪽 힙 최소 값이 작아질 때가 있는데
    # 그럴 경우 양쪽에서 heappop하여 반대쪽에 heappush해준다
    if rightheap and leftheap[0][1] > rightheap[0][1]:
        left = heapq.heappop(leftheap)[1]
        right = heapq.heappop(rightheap)[1]
        heapq.heappush(rightheap, (left, left))
        heapq.heappush(leftheap, (-right, right))
    print(leftheap[0][1])  # 짝수일 때, 홀수일 때 모두 왼쪽 힙 트리의 값이 말해야 하는 수가 된다

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!