[백준][BOJ1572] 중앙값

1. 문제 : https://www.acmicpc.net/problem/1572

1572번: 중앙값

---

2. 풀이 : Indexed Tree

---

3. 시간복잡도 :  O(NlogN)

---

4. 설명

단순하게 1부터 N까지 반복하면서 K개씩 정렬을하고 중앙값을 찾으면 풀릴 것 같지만 타임아웃이 발생하여 문제를 풀 수가 없다.

이 문제는 인덱스 트리에 K개의 입력값을 유지하면서 중앙값을 탐색하여 풀 수 있다.

N=6, K=3, 입력값의 범위 0 ~ 7, 입력값이 1, 0, 7, 3, 5, 4 일 때를 예로 들어보자.  입력값의 범위에 의해 입력값의 종류는 8개만 가능하며, 각 입력값의 위치를 그림[1]과 같이 리프에 표현할 수 있다.  

그림[1]

1번째 입력값 1 위치의 리프에 +1을 하여 1이 입력되었음을 그림[2]와 같이 표시한 후, 구간 합 트리를 갱신한다.

그림[2]

마찬가지로 2번째값인 0과 3번째값인 7의 리프에 +1을 하여 그림[3]과 같은 구간 합 트리를 만든다.

그림[3]

주어진 K=3의 조건이 만족되었으므로 트리의 루트에서부터 중앙값을 탐색한다. 루트값인 3은 구간 합 트리에 현재 3개의 입력값이 존재한다는 것을 의미하며, 루트의 왼쪽 자식 구간에는 2개의 입력값이, 루트의 오른쪽 자식 구간에는 1개의 입력값이 존재한다는 것을 알 수 있다. 따라서 구하려는 중앙값(2번째 값)은 왼쪽 자식인 1~4 구간에 존재한다는 것을 알 수 있다.

그림[4]

그림[4]와 같이 루트에서 왼쪽 자식인 노란 노드로 탐색을 한다. 노란 노드에서 왼쪽 자식 구간에 2개의 입력값이, 오른쪽 자식 구간에 0개의 입력값이 존재한다는 것을 알 수 있다. 따라서 중앙값(2번째 값)은 왼쪽 자식인 1~2 구간에 존재한다는 것을 알 수 있다.

그림[5]

그림[5]와 같이 노란 노드로 탐색을 한다. 노란 노드에서 왼쪽 자식 구간에 1개의 입력값이, 오른쪽 자식 구간에 1개의 입력값이 존재한다는 것을 알 수 있으며, 따라서 중앙값인(2번째 값)은 오른쪽 자식인 2~2 구간에 존재한다는 것을 알 수 있다.

오른쪽 자식을 탐색할 때는 주의할 점이 한 가지 있다. 왼쪽 자식의 구간에 1개의 입력값이 존재하므로 중앙값은 오른쪽 자식에서의 1번째 값으로 변경이 된다.

그림[6]

그림[6]에서 노란 노드는 리프 노드이므로 탐색을 종료하고, 해당 노드는 1의 위치 이므로 1을 return 해주며 이 값은 현재 입력값인 1, 0, 7의 중앙값임을 알 수 있다. 그리고 트리에서 1번째로 입력된 1의 리프에 -1을 하여 제거한 후, 4번째 입력값인 3의 리프에 +1을 하여  K=3 조건을 만족 시키고 그림[7]과 같이 중앙값을 탐색하면 0, 7, 3의 중앙값인 3이 return 된다.

그림[7]

위의 작업을 모든 입력값에 대하여 반복하면 중앙값은 다음과 같다.

그림[8]

그림[9]

따라서, 중앙값의 총합은 1 + 3 + 5 + 4 = 13이 된다.

---

5. 코드