[C++]이진 검색 트리(높이1) - 백준1539

문제

• 이진 검색 트리(백준1539)

풀이

문제 해석을 하자면,

• 입력으로 P배열이 주어지면, 이 배열을 통해서 이진 검색 트리를 만들었을때 각 노드들 높이의 총 합을 구하는 문제이다.
  • 문제 자체는 매우 간단해 보이는데, 전혀 쉽지 않았다,,

풀이

• 이 문제의 경우 구글링의 힘을 빌려서 해결하게 된 아쉬운 문제이다.
• 초기에는 직접 BST를 구현해서 시뮬을 돌렸는데 편향이진트리 때문에 N^2이라 시간초과 발생하였다..
• RBT는 NlogN이라 좋은데 BST의 높이와 달라서 정답이 틀릴테고..
  결국 구글링을 해보니 lower_bound 를 사용하는 방법으로 해결할 수 있다고 한다ㅜㅜ
  쉽다고 생각한건 큰 착각이였네 ,,
• (참고) 문제를 풀기 위해선 STL에서 제공하는 set, map을 공부할 필요가 있음.
  • 해당 자료구조는 RBT로 이루어져 있어서 insert, delete 등등 logN 연산을 보장!!
  • 그리고 높이는 https://blog.joonas.io/161 를 참고!!
    자신보다 바로 작거나 큰 수의 높이 중 큰 높이에 +1 을 하면 높이를 구할 수 있다.
  • 자신보다 바로 작거나 큰 수를 lower_bound를 통해서 logN 속도로 구할 수 있기 때문에 높이를 구하는것도 빠르게 구할 수 있다.
    • 트리를 inorder(중위순회) 해보면 오름차순으로 정렬되어 있음을 알 수 있고,
    • 때문에 당연히 lower_bound를 통해서 자신보다 바로 작거나 큰 수를 구할 수 있다.
    • 참고로 lower_bound가 왜 logN밖에 안걸리나??
      트리가(set,map) 정렬되어서 저장되어있기 때문에 이진 탐색을 하면 logN밖에 걸리지 않는다!
• 필자는 구조가 달라서 높이다르니까 RBT써도 못구할거라 생각했었다.
  • “높이가 자신보다 바로 작거나 큰 수의 높이 중 더 큰 높이에 +1” 을 통해서 구할 수 있다는걸 몰랐었고, 애초에 따로 배열에 높이를 기록해나가면 된다는것도 생각 못했었기 때문이다.

코드

#include<iostream>
#include<set>
using namespace std;

set<int> s; 
int heights[250002];

int main() {
	long long result = 0;
	int N;
	int inNum = 0;
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> inNum;
		
		auto iter = s.lower_bound(inNum);
		long long left, right;
		if (iter != s.begin()) { // s.begin()은 root주소
			auto left_iter = iter;
			left = heights[*(--left_iter)]; // 해당 위치의 값을 인덱스로 heights배열 접근
		}
		else {
			left = 0; // iter이 root면 left높이는 0
		}

		if (iter != s.end()) { // s.end()는 마지막 원소 다음 자리 주소
			right = heights[*iter];
		}
		else {
			right = 0; // iter이 마지막 원소 다음이란건 이미 최대크기 left를 구한상태
		}

		heights[inNum] = max(left, right) + 1;
		s.insert(inNum); // RBT에 삽입

		result += heights[inNum];
	}
	cout << result;
	return 0;
}

느낀점

이런 유형의 BST관련 문제들은 반드시 set, map 같은 자료구조로 해결하도록 익숙해지자.

직접 구현하는 것은 지양하도록 하자.