[C++]이진 탐색 트리(높이2) - 백준2957

문제

• 이진 탐색 트리(백준2957)

풀이

문제 해석을 하자면,

• 이전에 풀었던 이진 검색 트리(높이) 풀이 게시글을 참고하길 바람.

풀이

• 시간초과를 조심해야하는 문제(편향 트리같은것들 조심)!! 또한, 입출력 부터 크니까 조심.
• BST를 구현하는건 그만두고, 최대한 set or map 자료구조(RBT) 활용해보겠다.
  • RBT같은 균형트리는 편향 트리를 피할 수 있다.
• 문제를 보면, 카운터 C의 의미는 각 노드의 깊이(높이)를 해당 노드에 접근할때 까지 전부 더한 값이다.
  • 이 더하는 값을 순서대로 resultArr 에 기록해서 한번에 출력하겠다.
• 이전에 풀었던 이진 검색 트리(높이) 풀이 게시글을 참고해서 풀겠다.

코드

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

set<int> s;
int heights[300005];
long long resultArr[300005];

int main() {
	// 입출력 속도 개선
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	long long result = 0;

	int N;
	int inNum;
	cin >> N>>inNum; // 초기 inNum은 root값이고 C값이 루트 땐 0이다(문제확인)
	heights[inNum] = 0; // 따라서 root는 높이 0부터 시작하자.
	s.insert(inNum);
	resultArr[0] = 0;

	for (int i = 1; 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이 마지막 원소 다음이란건 원소가 없단것(빈 트리)
		}

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

		result += heights[inNum]; // 구한 높이들 더하는중(C 구하는중)
		resultArr[i] = result; // 순서대로 C 기록하는 중
	}

	for (int i = 0; i < N; i++) {
		cout << resultArr[i] << '\n';
	}

	return 0;
}

느낀점

생략