1572. 중앙값

1572번: 중앙값

---

길이 $N$인 수열에 대해 중앙값 내지는 중간값을 연속적으로 구하는 문제이다.

 

잘 알려진 대로(하지만 모르면 모르는) 세그먼트 트리를 응용하여 풀 수 있다. 값의 범위가 $[0,~65536]$으로 꽤 작아서, 각 값이 등장한 횟수를 저장해 놓은 뒤 합이 mid가 되는 최소의 인덱스를 찾으면 된다.

 

나는 ``std::multiset`` 두 개를 사용하여 풀었다. 길이 $K$인 구간을 ``left``와 ``right``로 쪼개어 반반씩 저장하고, ``left``는 내림차순으로, ``right``는 오름차순으로 정렬한다. 그러면 ``left``와 ``right``의 첫번째 값 중 하나가 중앙값이 것이다. 이제 값을 적절히 넣고 빼면서 중앙값을 구하면 된다.

 

말로 하기가 어려워서 코드를 첨부한다. 도저히 생각이 안 난다면 코드를 참고해 보자.

공유 소스 보기

---

6개월만에 메모리 초과 ㅋㅋㅋ