BOJ 2957. 이진 탐색 트리
최근 PS 재활치료를 하면서 기본기가 많이 부족하다는 것을 느꼈다.
당장 플레5 하나 잡고 풀어보려니까 뇌가 많이 아팠다.
이 문제같은 경우 PS할 때 한번은 짚고 넘어가면 좋을 것 같아서 복습 겸 정리를 해본다.
solved.ac: Platinum V (2024.09.10)
문제는 이거 구현해서 C값 출력하라는 것이다.
딱 봐도 그대로 구현하라는 문제는 절대 아니다. 편향 트리 반드시 주긴 할 거다.
먼저 저 카운터 값은 노드의 깊이를 의미한다는 것을 알 수 있다.
임의의 노드에 대해 자식이 존재한다면 왼쪽 자식은 반드시 노드보다 작고, 오른쪽 자식은 반드시 노드보다 크다.
일단 대충 트리가 있고, X가 삽입되는 상황이라고 가정해 보자.
어떤 노드 P에 대해 X < P이면 X는 P의 왼쪽 자식 노드로 들어갈 것이다.
만약 자식 노드가 없다면, X보다 큰 수 중 가장 작은 수는 P가 된다.
만약 X < Q < P인 Q가 존재한다고 가정해 보자.
Q는 P의 왼쪽 서브트리에 존재하지 않으므로 Q가 P의 조상이거나, 어떤 노드에 대해 서로 다른 서브트리에 위치해 있을 것이다.
먼저 Q가 P의 조상이면 X는 절대로 P에 도달할 수 없다.
P는 Q으 오른쪽 서브트리에 들어가게 될 것이고, X는 Q의 왼쪽 서브트리에 들어가게 된다.
따라서 이러한 경우는 생각하지 않는다.
만약 서로 다른 서브트리에 있다면, R = LCA(P, Q)이고 Q < R < P를 만족하는 R이 존재한다는 뜻이다.
이 경우 X < Q < R < P이므로 마찬가지로 R에서 Q가 존재하는 서브트리로 들어가게 되고, 마찬가지로 P에 도달할 수 없다.
따라서 이러한 경우도 모순이다.
즉 X < Q < P인 Q를 가정하면 두 경우 모두 말이 되지 않으므로 이러한 Q는 존재하지 않는다.
비슷한 방법으로 어떤 노드 S를 탐색 중인 X에 대해 S의 오른쪽 자식 노드가 없고, X > S면 S는 최댓값이 된다.
이제 X가 주어지면 X의 부모 노드 후보를 추릴 수 있게 되었다. 마지막으로 두 경우 중 하나를 골라야 한다.
L < X < H를 만족한다고 하고, L은 트리 내 원소 중 a < X를 만족시키는 a의 최댓값, H는 a > X를 만족시키는 a의 최솟값이다.
만약 depth[L] < depth[H]라 하자. 그러면 X가 L에 오면 L의 오른쪽 서브트리로 들어가고, 해당 서브트리에는 H가 존재하므로 H로 간다.
반대로 depth[L] > depth[H]라 하면 X가 H에 도달해서 왼쪽 서브트리로 들어간다.
즉 새로 생기는 X가 자리잡는 깊이는 max(depth[L], depth[H]) + 1이 된다.
이제 L, H를 빠르게 구해주면 끝난다.
문제는 난 여기서 처음에 <set>을 사용했고, 상큼한 TLE를 받았다.
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
typedef long long int LL;
set<int> arr;
int dep[300002];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
LL cnt = 0;
arr.insert(0); dep[0] = -1;
arr.insert(n + 1); dep[n + 1] = -1;
for(int i = 0; i < n; i++)
{
int cur;
cin >> cur;
auto hi = upper_bound(arr.begin(), arr.end(), cur);
auto lo = hi; lo--;
int d = max(dep[*lo], dep[*hi]) + 1;
cnt += d;
cout << cnt << '\n';
arr.insert(cur);
dep[cur] = d;
}
아무리 봐도 이론상 문제될 건 없어 보이는데, 시간초과를 받는다.
찾아보니 set이 logN이긴 한데 앞에 상수가 많이 붙는다고 한다. N도 30만으로 그렇게 작지 않다.
운이 정말 안 좋으면 터지기엔 충분한 시간복잡도였다.
그래서 set 대신 map을 사용했다. 이 경우 150ms 남짓으로 통과했다.
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
typedef long long int LL;
map<int, int> arr;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
LL cnt = 0;
arr[0] = -1; arr[n + 1] = -1;
for(int i = 0; i < n; i++)
{
int cur;
cin >> cur;
auto hi = arr.upper_bound(cur);
auto lo = hi; lo--;
int d = max(lo -> second, hi -> second) + 1;
cnt += d;
cout << cnt << '\n';
arr[cur] = d;
}
}
어디서 set 거르라는 글을 본 적이 있는 것 같긴 한데, 왜 그런 말이 있었는 지 알 것 같기도 하다.
대충 logN 어쩌고만 외우지 말고 이런 작은 점들도 공부해놓으면 좋을 것 같다.