https://www.acmicpc.net/problem/1572
1572번: 중앙값
중앙값이란, 수열을 정렬했고, 그 크기가 N일 때, 1부터 시작해서 (N+1)/2번째 있는 원소가 그 수열의 중앙값이다. 예를 들어, {1, 2, 6, 5, 4, 3}에서는 3이고, {11, 13, 12, 15, 14}에서는 13이다. 오세준은 1
www.acmicpc.net
세그먼트 트리 문제다.
풀이
[1321] 군인 문제와 [2243] 사탕상자 문제와 마찬가지로 최근 K개의 숫자 중 (K+1)/2 번째 숫자에 접근하면 된다. 0부터 65536의 숫자가 몇 개가 담겨있는지를 표현하는 구간 합 세그먼트트리를 생성. 이후 N개의 입력을 받으면서 세그먼트트리에 갱신해 준 뒤, 원소가 K개 이상일 때부터 (K+1)/2 번째로 작은 숫자를 계산하면 정답을 구할 수 있다.
여기서 중요한 점은 최근 K개까지가 범위이므로 중앙값을 반환할 때마다 (수열의 크기 - K) 번째 숫자를 세그먼트트리에서 하나씩 제거해주어야 한다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [1849] 순열 (0) | 2023.03.05 |
|---|---|
| [1517] 버블 소트 (0) | 2023.03.02 |
| [1321] 군인 (0) | 2023.02.28 |
| [2243] 사탕상자 (0) | 2023.02.28 |
| [3745] 오름세 (0) | 2023.02.26 |