[BOJ/Python] 백준 1655 가운데를 말해요

문제

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

풀이

풀이 1

• 37268 KB, 236 ms

import sys, heapq
input = sys.stdin.readline

n = int(input())
leftheap = [] # 최대힙
rightheap = [] # 최소힙
# rightheap[0]이 중간값이 되도록 입력하기 !!

for i in range(n) :
    x = int(input())

    if i == 0 :
        heapq.heappush(rightheap, x)
    else :
        if x < rightheap[0] :
            heapq.heappush(leftheap, x * (-1))
        else :
            heapq.heappush(rightheap, x)

        # push 하고 갯수 맞춰줘야함
        # rightheap이  한개 또는 두개 많도록
        if len(rightheap) <= len(leftheap) :
            tmp = heapq.heappop(leftheap) * (-1)
            heapq.heappush(rightheap, tmp)
        elif len(rightheap) - len(leftheap) > 2 :
            tmp = heapq.heappop(rightheap) * (-1)
            heapq.heappush(leftheap, tmp)

    print(rightheap[0])

풀이1 설명

백준 우선순위큐 카테고리에서 푼 문제. 도저히 모르겠어서 힌트 얻으려고 검색했다

• 아이디어 : 중앙값 기준으로 rightheap, leftheap을 구현 (절대값 힙 문제와 유사. 절대값 힙은 직접 풀었고 풀이 방법 떠올리는데도 시간이 별로 걸리지 않았는데 .. 여기서는 같은 방법 쓰는 것을 못 떠올려서 아쉽..)

• 주의사항

  • 중앙값이 rightheap 맨 앞에 오도록하려면, rightheap의 길이와 leftheap의 길이를 항상 유사하게 맞추어 주어야 한다
  • 길이를 맞추는 과정에서 각 heap의 요소를 pop & push 해주어야 하는데
  • 이때, leftheap에서는 항상 큰 값을 pop하게 되므로 최대힙으로 구현해주어야 한다