[c++] 백준 #2957 이진 탐색 트리 (190906)

< 풀이 >

map 연습문제이다. 삽입할 때마다 depth가 1증가하는데, 그만큼 counter가 증가한다는 사실을 이용해야 한다. key 값은 노드의 값, value는 depth 이런 식으로 map에 추가하면서 lower_bound를 사용해주면 된다. 약간 귀찮은 게 맨 첫번 째 원소 같이 앞에 값이 없는 경우. 예외처리만 잘 처리해주면 어렵지 않은 문제이다.

 

< 코드 >

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
#define pb push_back

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    // 숫자 하나씩 map에 삽입
    map<ll, ll > mymap;
    ll root; cin >> root;
    mymap[root] = 0;
    cout << "0\n";
    ll ctr = 0; // counter
    for(int i=1; i<N;i++){
        ll node; cin >> node;
        map<ll, ll>::iterator lower_iter;
        lower_iter = mymap.lower_bound(node); // 인자값보다 크거나 같은 값중에 가장 작은 값

        ll depth;
        if (lower_iter == mymap.end()) {
            lower_iter--;
            depth = lower_iter->second + 1;
        }
        else {
            depth = lower_iter->second + 1;
            if (lower_iter != mymap.begin()){
                lower_iter--;
                depth = max(depth, lower_iter->second + 1);
            }
        }
        mymap[node] = depth;
        cout << depth + ctr << '\n';
        ctr += depth;
    }
    return 0;
}