목록9426 (1)

[9426] 중앙값 측정

https://www.acmicpc.net/problem/9426 예전엔 중앙값 관련 문제 풀때 PQ 2개를 두고 풀거나 (최대/최소 중앙값을 찾는경우)parametric search로 풀었던것 같은데 오랜만에 중앙값 문제를 봐서 그런지 전에 풀었던 풀이가 기억이 나지않아 좀 다른 방법으로 풀었다. counting을 체크하는 리프노드가 65536개 짜리인 indexed tree를 구성하고, 최초 k개의 입력된 숫자를 indexed tree에 update한 뒤 중앙값인(k+1)/2번째 숫자가 어디있는지를 indexed tree에서 루트부터 역방향으로 내려오면서 탐색해서 중앙값을 찾아낸다. 마찬가지로 다음 수가 주어지면 그 수를 업데이트 해주고, 반대로 제일 먼저 들어왔던 첫번째 수를 빼주고 업데이트 하는식..
Algorithm/백준 온라인저지(BOJ) 2017. 3. 2. 20:33
이전 Prev 1 Next 다음