[프로그래머스/C++] 알고리즘 - 표현 가능한 이진 트리.

안녕하세요! 테크지니어22입니다.

오늘은 프로그래머스 알고리즘 - 표현 가능한 이진 트리를 풀어보도록 하겠습니다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/150367

프로그래머스

 

문제 접근

처음에는 삽질을 했습니다. 중위 순회를 파악해서 중위 순회한 트리를 원래 트리로 복원하는 방법도 고려해보았습니다.

하지만 이 문제의 핵심은 루트노드, 서브 루트 노드의 값을 살펴보는 것입니다.

리프노드를 제외한 서브 루트 노드들의 값이 1일 때 참입니다. 이때 루트 노드를 체크하고, 서브 루트 노드들을 계속해서 체크해야하기 때문에 DFS를 이용하였습니다.

추가로 엣지케이스를 고려해야 하는데 저도 이것을 빼먹어서 테스트케이스1번만 맞고 다 틀렸습니다.

바로 서브 루트 노드가 0이면, 그 노드의 서브 노드들이 모두 0이면 조건에 위배되지 않는다, 즉 참입니다.

 

풀이 전략

1.이진수 만들기

2.포화이진트리 수 만들기

3.루트 부모노드,서브노드 1 체크하기

4.서브 루트 노드가 0일 때, 그 노드의 서브 노드들이 모두 0 상황 체크하기

 

코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

vector<int> answer;
typedef long long ll; 

// 1.이진수 만들기
string binary_number(ll x) {
    string str = "";
    while(x > 0) {
        str = to_string(x % 2) + str;
        x /= 2;
    }
    return str;
}

bool is_full_len(ll n) {
    while(n > 1) {
        n = n-1 ;
        if(n % 2 == 1) return false;
        n /= 2 ; 
    }
    return true ; 
}

// 2.포화이진트리 수 만들기
string change_to_full_binary_tree(string s) {
    // 2^n-1 맞춰야함.
    while(true) {
        ll l = s.length() ; 
        if(is_full_len(l)) return s ;
        else s = "0"+s;
    }
}
// 4.루트 노드의 서브 트리 0 체크하기
bool isAllZero(string s){
    for(int i=0; i<s.size();i++){
        if(s[i]!='0'){
            return false;
        }
    }
    return true;
}

// 3.루트 부모노드,서브노드 1 체크하기
bool check(string s) {
    ll l = s.length();
    if (l == 1 ||isAllZero(s)) return true ; 
    ll mid = l / 2 ;     
    return (s[mid] == '1' && check(s.substr(0,mid)) && check(s.substr(mid+1,mid)));
}

vector<int> solution(vector<long long> numbers) {
   
    for(auto number: numbers) {
        string tmp = binary_number(number); 
        string str = change_to_full_binary_tree(tmp); 
        answer.push_back(check(str));
    }
    return answer;
}

 

배울점

- 엣지 케이스 고려하기