[백준] 2957번 : 이진 탐색 트리 - C++

백준 2957 : 이진 탐색 트리

등급 : Platinum V

2957번: 이진 탐색 트리 (acmicpc.net)

2957번: 이진 탐색 트리

사용 알고리즘 : -

사용 자료구조 : 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가 된다.

예시의 BST 입력 결과

---

#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";
    }
}