[1. 문제 설명]
아래 쿼리를 수행하는 프로그램을 작성한다.
A. 수열 S 에 자연수 X 를 추가한다. (append)
B. 수열 S 에 포함된 숫자 중 X 번째로 작은 수를 출력하고, 수열에서 제거한다.
[2. 풀이 접근]
간단한 풀이를 생각해보면, 트립(treap) 의 적용을 생각해 볼 수 있다.
트립을 통해 원소의 삽입과 삭제를 logN 에 할 수 있다.
또한 K번째 원소도 쉽게 찾을 수 있다.
그러나 구현이 살짝 까다로울 수 있으니, 나중에 다시 정리해보도록 하고,
구간 트리를 사용하여 풀이를 해볼 수 있다.
자연수 X 의 범위는 1 이상 2,000,000 이하이므로,
구간을 [1, 2,000,000] 을 하는 구간 트리를 생각 해 볼 수 있다.
각 노드가 저장하는 값은 구간이 포함하는 원소의 개수 이다.
예를 들면 아래와 같다.
구간 [1, 5] 가 3개의 원소를 포함하는데,
[1, 3] 구간은 2개의 원소 [4, 5] 구간은 1개의 원소를 포함한다.
root 노드를 통해 전체 몇개의 원소가 수열에 있는지 알 수 있으며,
leaf 노드에 저장 된 값이 하나 이상인 경우 leaf 가 가리키는 구간이 수열에 저장된 원소라 볼 수 있다.
(하나 이상이라는 것은 중복 된 원소가 수열에 저장되어 있음을 의미한다.)
즉, 쿼리 A 는 leaf 노드에 저장된 값에 +1 하고,
이 후, 구간 합을 갱신하도록 하면 된다.
쿼리 B 에 대한 처리는 아래와 같이 생각 해 볼 수 있다.
자연수 범위가 5 까지로 제한 된다고 하고,
수열에 [1, 2, 3, 4, 5] 가 저장되어 있다고 해보자
여기서 3번째 원소를 구하는 과정은 아래와 같다.
(노드에 적힌 숫자는 구간에 속한 원소의 개수)
루트를 기준으로 3번째 숫자는 왼쪽 트리에 존재한다.
=> 왼쪽으로 이동.
루트의 왼쪽 자식노드를 기준으로 3번째 숫자는 오른쪽 트리에 존재한다.
=> 오른쪽으로 이동
=> 단말 노드 => 3을 반환.
이번에는 4번째 숫자를 찾는 과정이다.
루트를 기준으로 4번째 숫자는 오른쪽 트리에 존재한다.
=> 오른쪽으로 이동
=> 루트를 기준으로 4번째 숫자는 오른쪽 자식 노드를 기준으로 첫번째 숫자이다.
오른쪽 자식 노드를 기준으로 1번째 숫자는 왼쪽 트리에 존재한다.
=> 왼쪽으로 이동
=> 단말 노드 => 4를 반환.
즉, 현재 노드를 기준으로 X 번째 노드를 찾는 것 인데,
왼쪽, 오른쪽에 저장 된 구간 합을 기준으로
어느쪽 으로 갈지 선택하는 것이며,
오른쪽으로 갈 때는 X 를 오른쪽을 기준으로 보정해야 한다.
마지막으로 생각할 부분은 수열에 중복된 값이 푸쉬 될 때이다.
이 경우는 간단하게 생각 할 수 있는데,
leaf 노드에 저장 된 값은 leaf 가 가리키는 구간(구간의 길이는 1 이므로 수열 내 원소를 의미함) 의 개수를 의미함으로,
이 값을 단순히 1만큼 증가시켜서 전체 트리를 업데이트 하면 된다.
(반대로 쿼리 B 를 실행하면 1 감소 시켜야 한다.)
[3. 코드]
'알고리즘 > Baekjoon' 카테고리의 다른 글
| 스위핑. [2170] (0) | 2022.11.04 |
|---|---|
| 구간 트리. [1168] (0) | 2022.11.03 |
| 구간 트리. [16975] (0) | 2022.11.01 |
| 구간 트리. [9345] (0) | 2022.10.31 |
| 구간 트리. [1517] (0) | 2022.10.30 |
