파이썬) 백준 알고리즘 | 2696번 : 중앙값 구하기

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

2696번: 중앙값 구하기

백준 2696 '중앙값 구하기' 문제입니다.

우선순위 큐를 이용하였는데 heap1, heap2를 만들고 heap1은 최대힙, heap2는 최소힙으로 구현합니다.

그리고 for문을 돌려서 홀수번째 수를 읽습니다.

첫번 째 수는 그냥 heap1에 넣고

두번 째부터는 각각 하나씩 heap1, heap2에 넣습니다.

그리고 heap1의 최댓값과 heap2의 최솟값을 꺼내서 비교한 뒤

만약 heap1의 최댓값이 heap2의 최솟값보다 크다면 heappop을 이용하여 각각 빼준 뒤에

heap1에 있던 걸 heap2에 heap2에 있던 걸 heap1에 넣습니다.

그렇게 계속 반복하다보면 heap1에 최댓값이 중앙값이 됩니다.

import sys
import heapq
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    nums = []
    heap1 = []
    heap2 = []
    answer = []
    m = int(input())
    for i in range(m//10+1):
        nums.extend(list(map(int, input().split())))
    for i in range(m//2+1):
        if len(heap1) < i+1:
            heapq.heappush(heap1, (-nums[2*i], nums[2*i]))

        if len(heap2) < i:
            heapq.heappush(heap2, nums[2*i-1])
        if i > 0:
            if heap1[0][1] > heap2[0]:
                a = heapq.heappop(heap1)
                b = heapq.heappop(heap2)
                heapq.heappush(heap1, (-b,b))
                heapq.heappush(heap2, a[1])
        answer.append(heap1[0][1])
    print(len(answer))
    for i in range(len(answer)//10+1):
        print(*answer[10*i:10*(i+1)])

처음으로 골드2 문제를 풀었습니다!

백준 플레 등급까지 파이팅!!