백준 9426 Java

문제

https://www.acmicpc.net/problem/9426

알고리즘 설명

세그먼트 트리 내에서 K 번째 값을 찾는 문제 (https://www.acmicpc.net/problem/2243 )
와 같은 맥락에서 접근 할 수 있다.
중앙 값 문제는 K 대신에 (K+1)/2 번째의 값을 찾으라는 말이다.

다만 길이가 K인 연속 배열 수열 에서 중앙값을 찾아야 하므로 중앙값 찾는 횟수를 N-K+1 번 해야한다는 것을 알 수 있다.

1. Segment Tree를 만들어놓고
2. 온도를 측정할때 마다 온도에 해당하는 leap 노드의 값을 1씩 update 해준다.
   언제까지? K 횟수동안.
3. K 횟수가 되면 중앙 값을 찾고
4. 가장 마지막에 했던 leap 노드 값을 없애주고, 다시 측정한 온도의 leap를 update 해주면서
   반복해주면 된다.

중앙값을 찾을때는
자식 노드의 값을 체크하면서 왼쪽 자식 값이 중앙값보다 크면 계속 왼쪽으로
오른쪽 자식 값이 크다면 중앙값에서 왼쪽 자식 값을 뺀 값을 찾는 value로 update 해준다.

   10      
  / \ 
 3   7

과 같은 노드에서 5번째 중앙 값을 찾고 싶다면 오른쪽에서 2번째 값(5-3) 이 중앙값이다.

구현 코드

https://github.com/melong222/SW/blob/master/SW/src/BACKJOON/B9426.java