[백준 2696] 중앙값 구하기

https://www.acmicpc.net/problem/2696 문제이해 수열을 읽으면서 홀수번째 수를 읽을때 현재까지 읽은 수열의 중앙값을 출력하라. 예) 수열 [1, 5, 4, 3, 2] 가 있을때 읽은횟수 읽어들인 수열 정렬 출력 1 [1] [1] 1 2 [1, 5] [1, 5] 3 [1, 5, 4] [1, 4, 5] 4 4 [1, 5, 4, 3] [1, 3, 4, 5] 5 [1, 5, 4, 3, 2] [1, 2, 3, 4, 5] 3 처음에는 읽어들인 수열의 개수가 홀수일때마다 정렬을해서 중간값을 출력하려했다.

그러나 테스트 케이스의 최대개수 1000개와 최대 수열의 크기 9999개라고 가정했을때 1000*9999**2을 했을때 약 100억 번의 연산횟수가 필요해 시간초과가 뜰거라고 생각했다. 다음으로 최소힙을 사용하려했는데 python에서 최소힙을 사용했을때 힙 배열에 저장되는 인덱스의 순서는 배열에 있는 모든 원소가 정렬되어있다고 보장해주지 않았다.

풀이 결국 블로그를 찾...