[c++] 백준 2957 - 이진 탐색 트리(map활용, 이후에 다시)

0. [c++] 백준  -

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

1. 풀이

처음에는 이진 탐색 트리를 직접 구현하여서 insert를 할 때마다 몇번의 노드 방문이 있는지를 계산하는 형태로 문제를 풀어보았다.

하지만, 이 방식은 최악의 문제 입력형태인 경우 시간초과를 면하기 힘든 구조를 가지고 있었다.

이진 탐색 트리의 경우 한쪽방향으로만 입력이 이루어지는 경우라면 O(N^2)의 시간복잡도를 가지게 되고, 이 문제의 경우 N = 300,000으로 대략 90억의 크기로 1억을 넘는 계산이므로 시간초과란 당연한 결과였다.

그럼, 이를 막기 위한 방법을 찾기 위해서 검색을 해보았는데, map이라는 컨테이너를 활욯하면 문제를 간단하게 접근할 수 있었다.

이 문제를 간단히 접근하기 위해서는 노드가 들어가는 위치가 어떻게 되는지를 판단해보아야 한다.

노드가 들어가는 위치는 항상 그 수에 인접한 두 노드 사이에 삽입되게 된다.

이러한 논리를 활용한 것이 map 컨테이너 인데, 이 컨테이너에서 lower_bound와 upper_bound는 인접한 노드 중 낮은 쪽, 높은 쪽의 iterator를 반환해주는 함수이다.

이 함수를 활용해 두 수중 더 depth가 깊은 쪽에 노드로 이 노드가 속하게 만들어주면 된다.

이러한 이유는, 두 노드 사이에 이 노드가 들어가게 되는데, 그 노드중 depth가 더 작은 노드는 더 큰 노드의 부모 노드에 위치해 있기 때문이다.

하튼, 이렇게 해서 코드를 작성하면, 원하는 결과를 얻을 수 있다.

+) 추가적으로 직접 map과 같이 최소 최대를 반환하는 형식의 컨테이너를 구현해보고 싶었는데, 이건 쉽지 않아서 이후에 다시 해보자.

2. 소스코드

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

#include <iostream> #include <algorithm> #include <map>   using namespace std;   map<int, long long int> MapArr; map<int, long long int>::iterator Lower_bound; map<int, long long int>::iterator Upper_bound;   int main(void) {     ios_base::sync_with_stdio(0);     cin.tie(0);     int N, temp;     long long int ret = 0;       MapArr.insert(pair<int, long long int>(0, -1));     MapArr.insert(pair<int, long long int>(300001, -1));     cin >> N;       for (int i = 0; i < N; i++) {         cin >> temp;         long long int depth = 0;         Lower_bound = (--MapArr.lower_bound(temp));         Upper_bound = (MapArr.upper_bound(temp));         dep = max(Lower_bound->second, Upper_bound->second) + 1;         MapArr.insert(pair<int, long long int>(temp, depth));         ret += depth;         cout << ret << "\n";     }       return 0; } Colored by Color Scripter

cs

3. 참고

http://www.cplusplus.com/reference/map/map/

http://www.cplusplus.com/reference/map/map/lower_bound/

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!