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

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

프로그래머스

<풀이>

1. 숫자들을 입력받는다.

2. 각 숫자를 하나의 이진트리로 표현할 수 있는지의 여부를 반환한다.

 

<해법>

1. 이진트리로 표현할 수 있는 수와 없는 수의 규칙 찾기

=> 번뜩이는 알고리즘이 떠오르지 않습니다. 따라서, 예제를 보면서 하나하나씩 직접 해보며 규칙을 찾아야합니다. 

7 = 111 (O)

42 = 0101010 (O)

5 = 101 (X)

그림과 쉽게 비교하기 위해 더미노드(0)도 추가했습니다. 규칙이 조금씩 보이시나요? 읽는 순서를 고려했을 때, 루트노드는 항상 2진수의 중앙에 옵니다. 루트노드에 더미노드(0)이 올 수 있을까요? 없습니다. 루트노드가 0인 수는 0뿐인데, 주어지는 숫자는 1이상 이기 때문입니다. 따라서, 규칙 하나를 찾았습니다. '2진수의 중앙은 0이 될 수 없다.'

 

두 번째 예시를 보며 규칙을 찾아보겠습니다. 

63 = 0111111 (O)

111 = 1101111 (O)

95 = 1011111 (X)

95는 2진수의 중앙이 1인데 불가능하다고 나옵니다. 왜일까요?

위와 같이 그려지기 때문입니다. 규칙 하나를 더 찾았습니다. '0이 1의 부모노드로 존재할 수 없다.' 또한, 그림을 직접 그려보면 트리를 왼쪽, 오른쪽 서브트리로 분할하고 정복해서 풀어야겠다는 느낌을 강하게 받을 수 있습니다. 그렇다면, 이제 어떻게 분할정복할지 알아보겠습니다.

 

2. 분할정복하는 방법

=> 위의 예시들로 몇가지 규칙을 찾았습니다. 찾은 규칙을 바탕으로 자세하게 분할정복하는 방법을 알아보겠습니다. 110 = 1101111을 예시로 들겠습니다.

(1) 분할하는 방법

110(왼쪽 서브트리) / 1(부모) / 111(오른쪽 서브트리) 로 분할합니다. 이후 왼쪽과 오른쪽을 정복한 후 이진트리로 표현할 수 있는지 판단합니다.

(2) 부모가 1인 경우

일단 이진트리로 표현할 수 있습니다. 왼쪽과 오른쪽 서브트리 또한 이진트리로 표현할 수 있다면, 이진트리로 표현할 수 있습니다.

(3) 부모가 0인 경우

부모가 0인 경우는 모두 불가능할까요? 아닙니다.

위와 같이 자식도 모두 0인 경우에는 이진트리로 표현할 수 있기 때문입니다. 따라서, 부모가 0인 경우에는 자식이 모두 0인 경우에는 가능하고, 나머지 경우는 불가능합니다.

 

3. 구현 전 정리

=> 아래는 구현 전 정리한 생각입니다.

(1) 주어진 숫자를 이진수로 만든다. (ex 5 -> 101) (코드의 hexToDec함수 참고)

(2) 만든 이진수를 포화 이진수로 만든다. 포화 이진수란 포화 이진트리로 표현할 수 있는 숫자이다. 포화이진트리의 노드 갯수는 2^n - 1개 입니다. 따라서, 포화이진트리 노드의 갯수에 맞춰서 앞에 0을 추가한다. (ex 11 -> 1011 -> 0001011) (코드의 changeToFullDec함수 참고)

(3) 만든 포화 이진수를 분할정복한다. 왼쪽, 중앙, 오른쪽으로 분할해서 정복한다. (ex 0001011 -> 000 / 1 / 011) (코드의 canDraw함수 참고)

자세한 구현은 아래 코드를 참고해주세요.

 

#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
string hexToDec(long long num);
string changeToFullDec(string str);
bool isAllZero(string str);
bool canDraw(string str);
 
vector<int> solution(vector<long long> numbers) {
    vector<int> answer;
    for (long long& num : numbers) {
        string dec = hexToDec(num);
        string fullDec = changeToFullDec(dec);
        answer.push_back(canDraw(fullDec));
    }
    return answer;
}
 
string hexToDec(long long num) {
    string ret = "";
    while (num) {
        ret = to_string(num % 2) + ret;
        num /= 2;
    }
    return ret;
}
 
string changeToFullDec(string str) {
    string ret = str;
    int idx = 2;
    while (true) {
        if (str.length() <= idx - 1) break;
        idx *= 2;
    }
    for (int i = 0; i < idx - 1 - str.length(); i++) ret = "0" + ret;
    return ret;
}
 
bool canDraw(string str) {
    if (str.length() == 1 || isAllZero(str)) return true;
 
    int midIdx = str.length() / 2;
    string left = str.substr(0, midIdx);
    string right = str.substr(midIdx + 1);
 
    if (str[midIdx] == '1' && canDraw(left) && canDraw(right)) return true;
    else return false;
}
 
bool isAllZero(string str) {
    for (char c : str) {
        if (c != '0') return false;
    }
    return true;
}

 

분할정복에 대해 알아볼 수 있는 문제였습니다.