[백준 2696번] 중앙값 구하기 (Python/파이썬)

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

2696번: 중앙값 구하기

우선순위 큐를 2개 이용하는 문제로 왼쪽은 최대힙, 오른쪽은 최소힙으로 구현하여 중앙값을 구했다.

양쪽 힙의 len이 같을때는 왼쪽에 heappush를 하고 나머지는 오른쪽에 넣어준다.

이때 왼쪽의 최댓값이 오른쪽의 최솟값보다 크면 둘의 위치를 바꿔준다.

위의 과정을 반복하므로써 중앙값을 우선순위 큐를 이용하여 구할 수 있다.

 

손으로 예시를 들어서 직접 써보면 이해하기 쉽다.

코드는 다음과 같다.

 

import sys
import heapq
input = sys.stdin.readline

def Sol():
  T = int(input())
  for _ in range(T):
    heapleft = []
    heapright = []
    mid = []
    M = int(input())
    sequence = list(map(int,input().split()))
    for i in range(M//10):
      sequence += list(map(int,input().split()))
      
    ## 양쪽 힙의 길이가 같으면 왼쪽에 heappush, 아니면 오른쪽에 heappush
    for i in range(len(sequence)):
      if len(heapleft) == len(heapright):
        heapq.heappush(heapleft, -sequence[i])
      else:
        heapq.heappush(heapright, sequence[i])
	
    ## 만약 왼쪽의 최댓값이 오른쪽의 최솟값보다 크면 자리 바꾸기
      if heapright and -heapleft[0] > heapright[0]:
        big = heapq.heappop(heapleft)
        small = heapq.heappop(heapright)
        heapq.heappush(heapleft, -small)
        heapq.heappush(heapright, -big)

      if (i+1)%2 == 1:
        mid.append(-heapleft[0])

    
    length = len(mid)
    if length > 10:
      start = 0
      end = 10
      print(length)
      for i in range(length//10):
        print(*mid[start:end])
        start += 10
        end += 10
      else:
        print(*mid[start:])
    else:
      print(length)
      print(*mid)

if __name__ == "__main__":
  Sol()

 

10개 단위로 입출력을 해야하므로 살짝 귀찮다. (다른방법으로 하신 분도 있으시겠지만)

완전 똑같은 문제로 1655번 가운데를 말해요가 있다.  복습용으로 풀기 좋으니 익숙하지 않다면 풀어보자.

 

글에대한 질문과 조언 모두 환영합니다!