Problem Solving/BOJ
1572. 중앙값
해스끼
2023. 4. 10. 22:17
1572번: 중앙값
중앙값이란, 수열을 정렬했고, 그 크기가 N일 때, 1부터 시작해서 (N+1)/2번째 있는 원소가 그 수열의 중앙값이다. 예를 들어, {1, 2, 6, 5, 4, 3}에서는 3이고, {11, 13, 12, 15, 14}에서는 13이다. 오세준은 1
www.acmicpc.net
길이 $N$인 수열에 대해 중앙값 내지는 중간값을 연속적으로 구하는 문제이다.
잘 알려진 대로(하지만 모르면 모르는) 세그먼트 트리를 응용하여 풀 수 있다. 값의 범위가 $[0,~65536]$으로 꽤 작아서, 각 값이 등장한 횟수를 저장해 놓은 뒤 합이 mid가 되는 최소의 인덱스를 찾으면 된다.
나는 ``std::multiset`` 두 개를 사용하여 풀었다. 길이 $K$인 구간을 ``left``와 ``right``로 쪼개어 반반씩 저장하고, ``left``는 내림차순으로, ``right``는 오름차순으로 정렬한다. 그러면 ``left``와 ``right``의 첫번째 값 중 하나가 중앙값이 것이다. 이제 값을 적절히 넣고 빼면서 중앙값을 구하면 된다.
말로 하기가 어려워서 코드를 첨부한다. 도저히 생각이 안 난다면 코드를 참고해 보자.
공유 소스 보기
www.acmicpc.net
6개월만에 메모리 초과 ㅋㅋㅋ