[python] 2696 - 중앙값 구하기

2696번: 중앙값 구하기 (acmicpc.net)

2696번: 중앙값 구하기

 

문제 접근을 완전 잘못해서 어려웠던 문제였다.

혼자 풀어낼 수 있었다면 좋았겠지만 그러지는 못했다.

 

우선 중앙값을 구하기 위해 우선순위 큐 2개를 사용하였다.

우선순위 큐의 사용이 자기 익숙지가 않아서 더 연습을 해봐야 할 것 같다.

 

우선 이 문제는 입력과 출력도 10개씩 끊어서 해야했기 때문에 조건을 추가해주었다.

문제를 풀기위한 가장 중요한 원리는 중앙값을 기준으로 양쪽으로 우선순위 큐가 존재할 때

 

[중앙값보다 작은 수들] - [중앙값] - [중앙값보다 큰 수들]

 

중앙값은 왼쪽 큐에서의 가장 큰 값과 오른쪽 큐에서의 가장 작은 값의 중간의 값이 된다는 것이다.

 

 그리고 항상 양쪽 큐의 개수를 맞춰 주어야 하기 때문에 

(왜냐하면 항상 홀수번째 수일때의 중앙값이므로!)

이 점에 유의해야 한다.

 

 

# 2696 중앙값 구하기
import sys, heapq
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    m = int(input())
    data=[]
    
    for i in range(m//10+1):
        data.extend(list(map(int, input().split())))
    
    left=[]    #중앙값보다 작은 수
    right=[]   #중앙값보다 큰 수
    mid=data[0] #첫번째 중앙값
    answer=[mid]    #결과값
    
    for i in range(1,m):
        if data[i] <= mid:
            heapq.heappush(left, -data[i])
        else:
            heapq.heappush(right, data[i])
            
        if i%2 == 0:
            if len(left)>len(right):
                heapq.heappush(right, mid)
                mid = -heapq.heappop(left)
            elif len(left)<len(right):
                heapq.heappush(left, -mid)
                mid = heapq.heappop(right)
            answer.append(mid)
    
    
    # 10개씩 끊어서 출력
    print(len(answer))
    for i in range(len(answer)):
        print(answer[i], end=' ')
        if(i+1) % 10 == 0:
            print()

 

다음에 다시 풀어보면 좋을 것 같은 문제였다.