[프로그래머스][C++] 표현 가능한 이진트리
표현 가능한 이진트리
문제 링크
분석
주어진 숫자를 이진수로 변환한 후, 포화 이진트리 형태로 표현할 수 있는지 판단하고, 반환해야합니다.
포화 이진트리는 모든 레벨에서 노드가 꽉 찬 이진트리를 의미합니다.
노드의 총 개수는 $2^h - 1$의 형태로, 1, 3, 7, 15, 31, ...입니다.
변환한 이진수는 트리를 중위순회(왼쪽, 부모, 오른쪽 순서로 살펴보는 것)한 결과와 같아야 합니다.
부족한 길이는 0으로 채워주어야합니다.
이진 트리에서 부모는 더미노드일 경우 그 자식 노드들또한 무조건 더미노드여야 합니다.
우선 주어진 십진수를 이진수로 변환해야합니다.
이후, 포화 트리의 노드 수에 맞춰주기 위해 자릿수가 부족한 경우 이진수 앞에 0을 채워주어 이진수의 길이를 맞춰줍니다.
마지막으로 트리의 부모가 0일 경우 자식 노드가 0인지 재귀적으로 검사해줍니다.
풀이
#include <string>
#include <vector>
using namespace std;
// 주어진 이진 문자열이 유효한 이진트리를 표현하는지 확인하는 함수
bool dfs(const string& tree)
{
int length = tree.length();
// 길이가 1이면 리프 노드이므로 항상 유효
if (length == 1)
{
return true;
}
// 현재 서브트리의 루트 노드는 가운데 위치의 노드
int mid = length / 2;
char root = tree[mid];
// 왼쪽 서브트리와 오른쪽 서브트리를 재귀적으로 분리
string left = tree.substr(0, mid);
string right = tree.substr(mid + 1);
// 각 서브트리의 유효성 검사
bool leftValid = dfs(left);
bool rightValid = dfs(right);
// 하나라도 유효하지 않다면 전체 트리는 유효하지 않다.
if (!leftValid || !rightValid)
{
return false;
}
// 현재 노드가 '0'이라면, 자식 노드들 중에 '1'이 있으면 안 된다.
if (root == '0')
{
if (left.find('1') != string::npos || right.find('1') != string::npos)
{
return false;
}
}
return true;
}
vector<int> solution(vector<long long> numbers) {
vector<int> answer;
for (long long number : numbers)
{
string binary = "";
// 숫자를 2진수 문자열로 변환
while (number > 0)
{
binary = to_string(number % 2) + binary;
number /= 2;
}
// 이진 문자열이 포화 이진트리를 만들 수 있는 길이로 확장될 수 있도록 길이를 계산
int h = 0;
while ((1 << h) - 1 < binary.length())
{
++h;
}
// 포화 이진트리를 만들 수 있는 최소 길이
int length = (1 << h) - 1;
// 이진 문자열의 앞에 필요한 만큼 0을 채워 길이를 포화 이진트리 노드 수와 같게 만든다.
binary = string(length - binary.length(), '0') + binary;
bool result = dfs(binary);
answer.push_back((result) ? 1 : 0);
}
return answer;
}
트리의 규칙상, 어떤 노드가 존재하지 않을때 0을 의미합니다.
그렇기 때문에 현재 노드가 ‘0’일 때, 자식 노드들 중에 ‘1’이 있으면 안 됩니다.
성능 요약
시간 복잡도는 $O(n)$입니다.
numbers를 순회하는 반복문 $O(n)$- 2진수 문자열로 변환하는 반복문 $O(l^2) \approx O(64^2)$
l은 2진수의 길이를 의미하며, 최대 64입니다.
- 포화 이진트리의 길이를 구하는 반복문 $O(h) \approx O(1)$
- 해당 반복문은 최대 7회 반복하는데, 8바이트 숫자의 최대 자릿수는 64이기 때문입니다.
- 0을 채워 넣어 길이를 노드 수와 같게 만들기 $O(m) \approx O(127)$
m는 포화 이진트리의 길이로 최대 127입니다.
- DFS 재귀 호출 $O(m \ log \ m) \approx O(127)$
- $O(n \times (O(l^2) + O(h) + O(m) + $O(m \ log \ m)))$
공간 복잡도는 $O(m \ log \ m)$입니다.
- 2진수 문자열과 포화 이진트리 문자열 $O(m) \approx O(127)$
- DFS 호출 스택 $O(h) \approx O(1)$
- DFS에서
substr로 인해 복사된 문자열 $O(m \ log \ m)$ - $O(m) + O(h) + O(m \ log \ m)$
테스트 성능
테스트 1 〉 통과 (0.02ms, 4.21MB)
테스트 2 〉 통과 (0.03ms, 4.15MB)
테스트 3 〉 통과 (0.05ms, 3.63MB)
테스트 4 〉 통과 (0.08ms, 4.15MB)
테스트 5 〉 통과 (0.25ms, 4.13MB)
테스트 6 〉 통과 (0.54ms, 4.14MB)
테스트 7 〉 통과 (0.70ms, 4.21MB)
테스트 8 〉 통과 (0.66ms, 4.15MB)
테스트 9 〉 통과 (2.93ms, 4.14MB)
테스트 10 〉 통과 (26.87ms, 5.77MB)
테스트 11 〉 통과 (48.07ms, 5.86MB)
테스트 12 〉 통과 (32.49ms, 5.61MB)
테스트 13 〉 통과 (24.17ms, 5.36MB)
테스트 14 〉 통과 (23.40ms, 5.39MB)
테스트 15 〉 통과 (17.19ms, 4.8MB)
테스트 16 〉 통과 (53.58ms, 5.79MB)
테스트 17 〉 통과 (51.08ms, 5.61MB)
테스트 18 〉 통과 (51.65ms, 5.4MB)
테스트 19 〉 통과 (43.07ms, 5.4MB)
테스트 20 〉 통과 (25.90ms, 4.55MB)
댓글남기기