[2957번] 이진 탐색 트리

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 빠른 이진 탐색 트리에 대한 이해 :: http://www.crocus.co.kr/641

2. Map STL

3. lower_bound 이해

위의 빨간 링크를 통해 이진 탐색을 어떻게 빠르게 처리할 지 우선적으로 생각해본다.

그 후 주석을 통해 내용을 확인해본다.(주석에 모든 내용을 다 기술해 두었습니다.)

---

이진 탐색 트리의 시간 복잡도

이진 탐색 트리는 트리의 구조에 따라 시간 복잡도가 달라진다.

삽입, 삭제

평균 :: 

최악(한 방향으로만 계속 뻗어있는 트리일 경우) :: 

이 이론적 알고리즘을 생각하고 이진 탐색 트리를 어떻게 하면 더 빠르게 삽입, 탐색을 가능하게 할 지 생각해보자.

 

아래 과정을 이해하고 접목한다면 삽입, 탐색이 최악과 관계없이 에 해결이 된다.

---

이 문제는 알고리즘 그대로를 이용한 코드로 문제를 제출할 시 으로 시간 초과(TLE)를 받게 된다.

따라서 아래의 코드를 통해 에 해결하도록 한다.

아래의 코드를 이용하면 결국 Tree의 구조까지 Map속에 있는 구조체에 의해 모두 파악할 수 있게 된다. 

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129

#include <iostream> #include <cstdio> #include <map>   using namespace std;   typedef struct _INFO_ {     int left;     int right;     long long int cnt; }INFO;   map<int, INFO> m;   int main() {     int n;     long long int ans = 0;       scanf("%d", &n);       for (int i = 0; i < n; i++)     {         int val;         int max = -1, min = -1;           scanf("%d", &val);           // 첫번째로 들어오는 값에 대한 예외 처리         if (!i)         {             m[val].cnt = 0;             printf("%lld\n", m[val].cnt);             continue;         }           // 반복자가 map의 끝을 가리키게 한다.         // it--를 하면 map에서 마지막 값을 가리키게 된다.         auto it = m.end();         it--;            // 마지막 값이 현재 들어온 값보다 작다면         // 현재 들어온 값보다 작은 것 중 가까운 값은 마지막 값이다.         // 현재 들어온 값이 가장 크니 max 는 없다.         if (it->first < val)         {             min = it->first;             max = -1;         }           // 마지막 값이 현재 들어온 값보다 크거나 같다면         // (이미 조건에서 같은 값은 들어오지 않는다고 되어있긴 하다.)         else         {             // lower_bound로 현재 들어온 값보다 크거나 같은 것 중              // 가장 가까운 값의 위치에 반복자를 설정한다.             it = m.lower_bound(val);               // 반복자가 map의 처음을 가리키고 있다면             // 현재 들어온 값이 가장 작은 값이라는 의미이므로 min은 없다.             // max는 map의 처음인 값이 현재 값보다 큰 값 중 가장 가까운 값이다.             if (it == m.begin())             {                 min = -1;                 max = it->first;             }               // 반복자가 map의 처음위치가 아닌 위치라면             // 즉, map의 처음과 끝이 아닌 사이의 값이 들어왔다면             // max는 현재 반복자가 가리키는 곳을 의미한다.             // min은 현재 반복자가 가리키는 바로 전 단계를 의미한다.             else             {                 max = it->first;                 it--;                 min = it->first;             }                      }           // 앞의 식으로 인해 구해진 min, max로 부터         // min과 max가 둘다 -1이 아니라면 즉, 사잇값이라면         if (min != -1 && max != -1)         {             // max의 왼쪽에 노드가 없다면 달아준다.             if (m[max].left == 0)             {                 m[max].left = val;                 m[val].cnt = m[max].cnt + 1;             }               // max의 왼쪽에 노드가 있다면             // min의 오른쪽에 노드가 달리는 것이 자명하다.             // (트리를 그려보면 알 수 있다.)             else             {                 m[min].right = val;                 m[val].cnt = m[min].cnt + 1;             }         }           // min만 -1이라면         // 즉, 가장 작은 값이라면         // max밖에 없으니 max의 왼쪽에 달린다.         else if (min == -1 && max != -1)         {             m[max].left = val;             m[val].cnt = m[max].cnt + 1;         }           // max만 -1이라면         // 즉, 가장 큰 값이라면         // min밖에 없으니 min의 오른쪽에 달린다.         else if (min != -1 && max == -1)         {             m[min].right = val;             m[val].cnt = m[min].cnt + 1;         }           // 결과 값을 누적한다.         ans += m[val].cnt;         printf("%lld\n", ans);     }       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

일반 알고리즘을 이용한 소스 코드(TLE) : 

#include <iostream>
#include <cstdio>
#include <map>
 
using namespace std;
 
typedef struct _INFO_ {
    int left;
    int right;
    int cnt;
}INFO;
 
map<int, INFO> m;
 
int main()
{
    int n;
    int ans = 0;
    
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
    {
        int val;
        int max = -1, min = -1;
 
        scanf("%d", &val);
 
        if (!i)
        {
            m[val].cnt = 0;
            printf("%d\n", m[val].cnt);
 
            continue;
        }
 
        for (auto it = m.begin(); it != m.end(); it++)
        {
            if (it->first < val)
                min = it->first;
 
            else if (max == -1 && it->first > val)
                max = it->first;
 
            if (min != -1 && max != -1)
                break;
        }
 
        if (min != -1 && max != -1)
        {
            if (m[max].left == 0)
            {
                m[max].left = val;
                m[val].cnt = m[max].cnt + 1;
            }
            else
            {
                m[min].right = val;
                m[val].cnt = m[min].cnt + 1;
            }
        }
 
        else if (min == -1 && max != -1)
        {
            m[max].left = val;
            m[val].cnt = m[max].cnt + 1;
        }
 
        else if (min != -1 && max == -1)
        {
            m[min].right = val;    
            m[val].cnt = m[min].cnt + 1;
        }
 
        ans += m[val].cnt;
        printf("%d\n", ans);
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>