허비의 기술블로그

-10,000 ~ 10,000 사이의 정수 N개가 입력으로 들어오면, 숫자 입력이 차례로 들어올 때마다 중앙값을 출력하는 문제다. ex) input : 3 6 8 4 5 6 2 output : 3 3 6 4 5 5 5 입력이 짝수개가 들어왔을 때는 중간의 두 수중 작은 수를 출력한다. 시간 복잡도: O(NlogN) 풀이 방법 출력해야 하는 값은 중앙값이다. 제일 간단히 중앙값을 찾는 방법은, 입력이 들어올 때마다 들어온 입력값들을 정렬한 후에 가운데 값을 출력하는 것이지만 그러면 매 입력마다 O(NlogN)의 시간이 걸리고 총 O(N^2 * logN)의 시간이 걸려서 시간 초과가 발생한다. Heap 자료구조를 이용하면 삽입, 삭제를 O(logN) 시간에 할 수 있으며 구현 방법에 따라 MinHeap, M..