[백준] 2957번: 이진 탐색 트리, 1539번: 이진 검색 트리 | C++

 

2957번: 이진 탐색 트리

1539번: 이진 검색 트리

거의 같은 문제!

 

 

틀린 이유

처음에 2957번 문제를 풀 때 그냥 BST를 구현했었다.

#include<iostream>
#include<vector>
#include<algorithm>
#define MAX 100000
#define fse(A,B,C) for(int i=A;i<B;i+=C)
using namespace std;
int counter;
class Node{
    int value;
    Node* children[2];
    public:
    Node(int v){
        this->value=v;
        children[0]=NULL;
        children[1]=NULL;
    }

    void insert(int v){
        counter++;
        int idx=(this->value > v)? 0:1;
        
        if(this->children[idx] == NULL){
            this->children[idx]=new Node(v);
        }else{
            this->children[idx]->insert(v);
        }
    }
};
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int N;
    cin>>N;

    int value;
    cin>>value;
    Node* root=new Node(value);
    cout<<counter<<'\n';
    fse(0,N-1,1){
        cin>>value;
        root->insert(value);
        cout<<counter<<'\n';
    }
}

그러고 당연히 시간초과가 났다. 1,2,3, ... N 이 입력되면 최악 O(N^2)인 시간복잡도를 가지는 것을 간과했다.

 

 

정답코드

찾아보니 균형이진트리를 사용해야 한다고 한다. "트리로 구현된 set, map" 태그가 뭔가 싶었는데, c++의 STL map과 set은 레드블랙트리로 구현됐다고 한다! STL을 사용해 간단(?)하게 구현 가능하다.

#include<iostream>
#include<vector>
#include<algorithm>
#define MAX 300000
#include<map>
#define fse(A,B,C) for(int i=A;i<B;i+=C)
using namespace std;
typedef long long ll;
map<int,ll> counter;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int N;
    cin>>N;
    counter.insert({0,-1});
    counter.insert({N+1, -1});
    ll answer=0;

    fse(0,N,1){
        int value;
        cin>>value;
        auto r_iter=counter.upper_bound(value);
        auto l_iter=r_iter;
        l_iter--;

        ll tmp=max(r_iter->second, l_iter->second)+1;
        answer+=tmp;
        cout<<answer<<"\n";
        counter.insert({value, tmp});
    }
}

출력하는 값은 노드가 삽입된 깊이의 누적값이다. 깊이 카운팅은 int 값을 벗어날 수 있다. 찾으려는 값의 upper_bound와 lower_bound 최댓값이 삽입될 노드의 부모 높이가 된다. 

 

 

map에서upper_bound, lower_bound 사용은 벡터와는 다르니까 익혀두자.

>>> map에서 upper_bound

https://cplusplus.com/reference/map/map/upper_bound/

https://cplusplus.com/reference/map/map/upper_bound/