문제 링크입니다: https://www.acmicpc.net/problem/2957
2957번: 이진 탐색 트리
문제 이진 탐색 트리는 모든 노드가 많아야 2개의 자식 노드를 가지고 있는 트리이고, 각 노드에는 수가 하나씩 쓰여있다. 만약 어떤 노드에 쓰여 있는 수가 X라면, 그 노드의 왼쪽 서브트리에는 X보다 작은 수, 오른쪽 서브트리에는 X보다 큰 수만 저장되어 있어야 한다. 1보다 크거나 같고, N보다 작거나 같은 수 N개가 한 번씩 등장하는 수열이 입력으로 주어진다. 이 수열을 이용해서 이진 탐색 트리를 만들려고 한다. 이제 배열의 첫 번째 수를 루트 노드로
www.acmicpc.net
N은 최대 300,000이고 이진 탐색 트리를 구성할 때 최악의 경우 skewed binary tree가 되기 때문에 시간복잡도가 O(N^2)이 될 수가 있습니다.
따라서, upper_bound를 이용해 풀어야하는 문제였습니다.
처음 들어오는 숫자는 무조건 root가 되고,
이후에 들어오는 숫자는 upper_bound를 이용해 아래와 같은 두 조건을 검사해야합니다.
i) 트리 내 제일 큰 숫자가 아닐 경우
ii) 트리 내 제일 작은 숫자가 아닐 경우
검사한 두 조건에서 구한 높이 중 더 높은 값을 C에 더하고 해당 숫자는 그 높이에 있는 노드의 자식노드이기 때문에 map에 저장할 때는 (해당 높이 + 1)을 저장해줘야합니다.
* kks227님 풀이를 참고해서 풀었습니다. 항상 감사합니다.
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 6087번 레이저 통신 (0) | 2019.10.13 |
|---|---|
| 백준 1981번 배열에서 이동 (2) | 2019.10.08 |
| 백준 2933번 미네랄 (0) | 2019.10.07 |
| 백준 2186번 문자판 (7) | 2019.10.03 |
| 백준 5635번 생일 (2) | 2019.10.02 |