11_30<백준>2957번 이진 탐색 트리

출처:https://www.acmicpc.net/problem/2957

문제

이진 탐색 트리는 모든 노드가 많아야 2개의 자식 노드를 가지고 있는 트리이고, 각 노드에는 숫자가 하나씩 쓰여있다. 만약 어떤 노드에 써있는 숫자가 X라면, 그 노드의 왼쪽 서브트리에는 X보다 작은 수, 오른쪽 서브트리에는 X보다 큰 수만 저장되어 있어야 한다.

1보다 크거나 같고, N보다 작거나 같은 수 N개가 한 번씩 등장하는 수열이 입력으로 주어진다. 이 수열을 이용해서 이진 탐색 트리를 만드려고 한다. 즉, 수열의 첫번째 숫자부터, 마지막 숫자까지 이진 탐색 트리에 넣는 것이며, 각 숫자에 대해서 insert(X, root)를 차례대로 호출하는 것이다.

이진 탐색 트리에 삽입하는 함수는 다음과 같다.

insert(number X, node N)
    카운터 C값을 1 증가시킨다
    if X가 노드 N에 있는 숫자보다 작다면
        if N의 왼쪽 자식이 없다면
            X를 포함하는 새 노드를 만든 뒤, N의 왼쪽 자식으로 만든다
        else
            insert(X, N의 왼쪽 자식)
    else (X가 노드 N에 있는 숫자보다 크다면)
        if N의 오른쪽 자식이 없다면
            X를 포함하는 새 노드를 만든 뒤, N의 오른쪽 자식으로 만들기
        else
            insert(X, N의 오른쪽 자식)

        

각 숫자를 삽입한 후에 C의 값을 출력하는 프로그램을 작성하시오. 카운터 C의 값은 0으로 초기화되어 있다.

문제 해결 과정:

-주어진 수도코드로 함수를 삽입할 경우 시간초과가 뜬다.

-이는 최악의 경우 O(n^2)인데 30만까지 입력될경우 시간제한 1초를 넘겨버린다.

- 결국 카운트는 깊이를 더하는 것이므로 각 숫자의 깊이를 비교하여 넣는다. 이떄 map을  사용한다.

#include<iostream>
#include<map>
#include<algorithm>
#include<cstdio>
 
using namespace std;
 
int main() {
    int capacity;
    scanf("%d",&capacity);
    long long int C = 0;
    map<int,long long int> mapAr;
    map<int,long long int>::iterator lower_bound;
    map<int,long long int>::iterator upper_bound;
    mapAr.insert(pair<int,long long int>(0, -1));
    mapAr.insert(pair<int,long long int>(300001, -1));
    for (int i = 0; i < capacity; i++) {
        int a;
        scanf("%d", &a);
        long long int dep;
        lower_bound = (--mapAr.lower_bound(a));
        upper_bound = (mapAr.upper_bound(a));
        dep = max(lower_bound->second, upper_bound->second) + 1;
 
        mapAr.insert(pair<int, long long int>(a, dep));
        C += dep;
        printf("%lld\n", C);
    }
 
}

참고:http://vvshinevv.tistory.com/27

원래 나의 코드:

#include<iostream>
using namespace std;
 
struct Node {
    int val;
    Node* left = NULL;
    Node* right = NULL;
};
class BinaryTree{
private: 
    Node* root;
    int cnt = 0;
public:
    BinaryTree() {
        root = NULL;
    }
    BinaryTree(Node* r) {
        root = r;
    }
 
    void insert(int n, Node* current) {
        cnt++;
        if (current->val > n) {
            if (current->left == NULL) {
                Node* temp = new Node;
                temp->val = n;
                current->left = temp;
            }
            else {
                insert(n, current->left);
            }
        }
        else if( n> current-> val) {
            if (current->right == NULL) {
                Node* temp = new Node;
                temp->val = n;
                current->right = temp;
            }
            else {
                insert(n, current->right);
            }
 
        }
    }
 
    Node* getRoot() {
        return root;
    }
    int getCnt() {
        return cnt;
    }
};
 
int main() {
    int capacity;
    cin >> capacity;
    int root;
    cin >> root;
    Node* x = new Node;
    x->val = root;
    BinaryTree a(x);
    cout << 0 << endl;
    int val;
    for (int i = 0; i < capacity - 1; i++) {
        cin >> val;
        a.insert(val, a.getRoot());
        cout << a.getCnt()<<endl;
    }
    
}