[백준/Python] 2696번 중앙값 구하기

문제링크

2696번: 중앙값 구하기

참고자료

http://mwultong.blogspot.com/2007/06/median.html

중앙값이란? 통계에서 중간값, 메디안의 의미; Median

https://sanghoon9939.tistory.com/32

Baekjoon-2696)중앙값 구하기

 

중앙값이란?

처음에 중앙값이 무엇을 의미하는 지 알지 못해서 문제자체를 이해를 못했다.

중앙값은 영어로 Median 이라고도 하는데 여러개의 숫자들이 있을때, 그 숫자들을 우선 크기순으로 정렬한 다음 가장 가운데 위치한 숫자를 1개만 콕 찝어서 골라낸 값이다.

 

홀수일때

숫자들이 홀수개 있을때는 크기순으로 가장 가운데의 숫자를 골라내면된다. 

짝수일때

짝수라면 가운데 숫자가 없기때문에 가장 가운데의 양쪽 숫자를 선택한 후 평균을 구한다.

 

중앙값 구하는 알고리즘

https://sanghoon9939.tistory.com/32

Max Heap 에는 중앙값 이하의 값들이 들어간다.

Min Heap은 중앙값보다 큰 값이 들어간다.

 

https://sanghoon9939.tistory.com/32

1. 새로운 값을 입력할때 Heap 사이즈가 다르다면 Max Heap()의 top값과 새로운값을 비교합니다.

2. 만약 새로운 값이 더 크다면 Min Heap 에 넣어줍니다. 

3. 작거나 같다면 Max Heap 의 top 값을 Min Heap 으로 옮겨주고 새로운 값은 Max Heap 으로 넣습니다.

 

https://sanghoon9939.tistory.com/32

1. 새로운 값을 입력할때 2개의 Heap 사이즈가 같다면 Min Heap의 top 값과 새로운 값을 비교합니다.

2. 만약 새로운 값이 더 작다면 Max Heap 에 넣어 줍니다.

3. 크거나 같다면 Min Heap의 top을 Max Heap 으로 옮겨주고 새로운 값은 Min Heap으로 넣습니다.

 

https://sanghoon9939.tistory.com/32

새로운 값을 넣고 난후 두 Heap 사이즈가 다르다면 Max Heap의 top 값이 중앙 값이 됩니다.

 

추가적인 부분

자바스크립트에서는 2차원배열을 1차원 배열로 바꿀때 flat() 메소드를 사용하거나 배열을 합칠때 스프레드 연산자를 사용하면 되는데, 파이썬에서는 배열을 합치려면 어떻게 해야하는지 알지 못했다.

파이썬에서는 extend 라는 메소드를 사용해서 배열 두개를 합칠 수가 있었다.

문제풀이

import sys
import heapq
input = sys.stdin.readline

num = int(input())

for i in range(num):
    maxh = []
    minh = []
    result = []
    count = 2
    caseN = int(input())
    caseNum = caseN // 10
    arr = []
    for i in range(caseNum+1) :
        arr.extend(list(map(int,input().split())))
    median = arr[0]
    heapq.heappush(maxh,-1*median)
    result.append(median)
    for i in range(1,len(arr)) :
        if count % 2 == 0:
            if arr[i] > -1*maxh[0] :
                heapq.heappush(minh,arr[i])
            else :
                heapq.heappush(minh,-1*heapq.heappop(maxh))
                heapq.heappush(maxh,-1*arr[i])

        else :
            if arr[i] > minh[0]:
                heapq.heappush(maxh,-1*heapq.heappop(minh))
                heapq.heappush(minh,arr[i])
            else:
                heapq.heappush(maxh,-1*arr[i])
            result.append(-1*maxh[0])
     
        count +=1
    print((caseN+1)//2)
    row = len(result) // 10
    answer=''
    for i in range(row):
        for j in range(10):
            answer += str(result[i*10+j])+" "
        answer+="\n"
    for i in range(row*10,len(result)) :
        answer += str(result[i])+" "
    print(answer)