티스토리 뷰
백준 2957 : 이진 탐색 트리
등급 : Platinum V
사용 알고리즘 : -
사용 자료구조 : Map
이진 탐색 트리의 구조와 특성을 물어보는 문제.
이진 탐색 트리에 자료가 들어가는 구조와 upper_bound를 알고있으면 쉽게 풀 수 있다.
1. Key에 삽입되는 Node 이름, Value에 Depth를 입력해주기 위해 map <int, int>를 선언.
2. 1≤N≤300,000이므로 0과 300,001 자리에 -1 Value를 넣어 저장해준다.
( 양 옆 수의 Depth를 비교해야 하는데, 경계선이 없으면 비교할 수 없기 때문 )
3. 수를 넣을 때 현재 들어갈 Key값의 upper_bound를 구해 오른쪽에 있는 수의 깊이를 확인한다.
4. upper_bound의 iterator를 감소시켜 왼쪽에 있는 수의 깊이도 확인한다.
5. 두 깊이를 비교하여 더 큰 값에 1을 더해준다.
6. 더해준 값을 Value로 해 Key와 함께 map에 넣어준다.
7. 이 깊이가 탐색 횟수가 되므로, 이를 결과값에 누적시켜주고 이를 반복한다.
※ N의 범위가 최대 300,000이므로 출력값은 int값을 넘어갈 수 있다. (0부터 299,999까지의 합) → long long 타입으로 지정
예시) N=8, <3, 5, 1, 6, 8, 7, 2, 4> 순으로 입력되는 경우.
1. 3을 입력하기 위해 3이 입력될 위치의 양 옆에 입력된 값의 Depth를 확인 후 입력.
→ (0, -1), (300001, -1) 이므로 3의 Depth는 max(-1, -1) + 1인 0이 된다.
→ ans에 Depth값을 더하고 출력해준다. ans의 초기값은 0이므로 0+0=0.
2. 5를 입력하기 위해 5가 입력될 위치의 양 옆에 입력된 값의 Depth를 확인 후 입력.
→ (0, -1), (3, 0) 이므로 5의 Depth는 max(-1, 0) + 1인 1이 된다.
→ ans에 Depth값을 더하고 출력해준다. ans + 1 = 1.
3. 1을 입력하기 위해 1이 입력될 위치의 양 옆에 입력된 값의 Depth를 확인 후 입력.
→ (0, -1), (3, 0) 이므로 1의 Depth는 max(-1, 0) + 1인 1이 된다.
→ ans에 Depth값을 더하고 출력해준다. ans + 1 = 2.
4. 6을 입력하기 위해 6이 입력될 위치의 양 옆에 입력된 값의 Depth를 확인 후 입력.
→ (5, 1), (300001, -1) 이므로 max(1, -1) + 1인 2가 된다.
→ ans에 Depth값을 더하고 출력해준다. ans + 2 = 4.
이와 같은 방법으로 해나갈 때, 출력은 0 1 2 4 7 11 13 15가 된다.
#include <iostream>
#include <map>
using namespace std;
#define ll long long
map <int, int> m;
map <int, int> ::iterator upper, lower;
// 양 옆의 주소값을 구하기 위해 iterator 변수 지정
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, x;
ll ans = 0;
cin >> n;
m.insert({0, -1});
m.insert({300001, -1});
// 양 끝의 경계에 최소값을 넣어준다
for (int i = 0; i < n; i++)
{
cin >> x;
upper = m.upper_bound(x);
lower = upper--;
int val = max(upper->second, lower->second) + 1;
// 양 옆의 노드의 깊이를 확인하고 더 큰 깊이에 1을 더한 값을 Depth로 지정
m.insert({ x, val });
ans += val;
cout << ans << "\n";
}
}
'알고리즘 > 코딩테스트' 카테고리의 다른 글
[백준] 1080번 : 행렬 - C++ / JAVA (0) | 2022.12.14 |
---|---|
[백준] 1062번 : 가르침 - C++ (0) | 2022.12.07 |
[백준] 12852번 : 1로 만들기 2 - C++ (0) | 2022.12.02 |
[백준] 12100번 : 2048 (Easy) - C++ (0) | 2022.11.30 |
[백준] 4196번 : 도미노 - C++ (0) | 2022.11.30 |