BOJ 가운데를 말해요 골드 2

우선순위 큐

import heapq -> 배열을 이용하여 우선순위를 만드는 것. v[0] 은 항상 최솟값(최댓값)을 유지하지만 나머지 index 들은 순서를 유지할 거라는 보장이 없다. default 는 최소힙

문제풀이

두개의 우선순위 큐를 중앙값을 기준으로 left 와 right로 나눠서 관리한다.
left 에는 중앙값보다 작거나 같은 값들이, right 에는 중앙값보다 큰 값들이 들어가게 되는데,
이를 비교하기 위해서는 left 의 가장 큰 값과 right의 가장 작은 값을 비교해야 한다.
-> left 는 최대힙, right는 최소힙으로 구현한다.

import sys
import heapq as hq
input = sys.stdin.readline

n = int(input())

left = [] # 최대힙
right = [] # 최소힙
for _ in range(n):
    num = int(input())
    if len(left) <= len(right): # push to left
        hq.heappush(left, (-num, num))
    else: # push to right
        hq.heappush(right, (num, num))

    if right:
        l, r = hq.heappop(left)[1], hq.heappop(right)[1]
        l, r = min(l,r), max(l,r)
        hq.heappush(left, (-l, l))
        hq.heappush(right, (r, r))

    print(left[0][1])

비슷한 문제

BOJ 키로거

역시 cursor 를 기준으로 left, right 를 이용. 단 우선순위 대신 deque를 사용했다.

import sys
from collections import deque
input = sys.stdin.readline

ntest = int(input())

def getPassword(s):
    left, right = deque([]),deque([]) # cursor 를 기준으로 왼쪽, 오른쪽

    for ch in s:
        if ch == '<':
           if left:
                right.appendleft(left.pop())
        elif ch == '>':
            if right:
                left.append(right.popleft())
        elif ch == '-':
            if left:
                left.pop()
        else:
            left.append(ch)
    return ''.join(left) + ''.join(right)



for _ in range(ntest):
    print(getPassword(input().strip()))