[baekjoon] 1655 - 가운데를 말해요

가운데를 말해요

우선순위 큐

 

python3

from sys import stdin
n = int(stdin.readline())
nums = []

# 삽입할 위치를 찾는 함수. 약간 binary search 흉내낸..
def bs(n, l, r, numbers):
    # n과 가장 가까운 숫자가 위치한 인덱스를 찾은 경우
    if l == r:
        if n < numbers[l]:
            return l
        else:
            return l + 1

    m = (l + r) // 2
    
    # 수빈이가 같은 숫자를 여러번 말하지는 않기 때문에, n == numbers[m]은 따로 처리하지 않음.
    if n <= numbers[m]: 
        return bs(n, l, m, numbers)
    elif numbers[m] < n:
        return bs(n, m + 1, r, numbers)


def find_index(n, numbers):
    if len(numbers) == 0:
        return 0
    return bs(n, 0, len(numbers) - 1, numbers)

for _ in range(n):
    target = int(stdin.readline())
    result = find_index(target, nums)
    nums.insert(result, target)
    center = None
    length = len(nums)
    middle = length // 2
    if length % 2 == 0:
        print(nums[middle-1:length][0])
    else:
        print(nums[middle])

원소를 삽입할 때 마다, 순서를 유지하면 중간값 가져오는것은 엄청 쉽다.

그런데 파이썬이라 그런지 바로 시간초과.

병신같은 백준 stdio는 덤.