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

처음에 문제이해를 잘못해서 헤맸다..!

(0이 오른쪽에도 추가될 수 있다고 생각했다...!)

 

우선 더미노드를 추가해서 포화이진트리 상태를 만들어줘야한다.

더미노드는 가장 왼쪽에만 추가해야지 원래 숫자가 다른 값으로 바뀌지 않는다.

포화이진트리의 개수를 보고 추가해야 할 더미노드 개수를 구한다.

(fillDummy()함수가 여기에 해당한다.)

 

*예시*

포화이진트리의 개수는 depth에 따라 1, 3, 7, 15...이 된다.

숫자 10에 더미노드를 추가하게 되면, 숫자 10은 이진수로 나타내면 1010이고,

7개의 노드를 갖는 depth3의 포화이진트리로 1010을 표현할 수 있기때문에

앞에 더미노드 3개가 들어가 0001010로 값을 바꿔준다.

 

더미노드가 추가됬다면, 해당 값이 이진트리가 맞는지 확인을 해야한다.

이진트리 여부를 확인하기 위해 루트노드와 왼쪽트리, 오른쪽트리를 나눠서 분할 정복했다.

루트노드가 1이면 왼쪽트리와 오른쪽트리가 각각 이진트리가 맞는지 확인을 한다.

이진트리여부 확인은 다음과 같다.

 

1. 길이가 3보다 작으면 가장 하단의 리프 노드여서 return 1

2. 확인하는 트리에 원소로 1이없으면 모두 0인 경우이므로 return 1

(모두 0값이면 이진트리이므로)

3. 해당 트리의 루트요소가 1이면, 왼쪽트리와 오른쪽트리에 대해서도 이진트리여부를 확인한다.

4. 해당 트리의 루트요소가 0이면, 부모노드가 0인데 자식노드가 1인 경우가 있으므로 이진트리가 아니다.

(2에서 모두 0인 경우는 제외했으므로, 여기서는 자식노드 중 하나라도 1인 노드가 있다)

(check_binary함수 재귀)

 

 

*string앞에 값을 넣는것보다 뒤에 값을 넣는 것이 효율적이라 코드에서 이진수는 뒤집힌 상태다. 

ex) 숫자 10은 0101000

#include <string>
#include <vector>

using namespace std;
string fillDummy(string x){
  int len = x.length();
  int k = 1;
  while(len - k > 0){
    len -= k;
    k = k*2;
  }
  for(int i=0; i<k-len; i++)
    x += "0";
  return x;
}
int check_binary(string x){
  int len = x.length();
  if(len < 3)
    return 1;
  if(x.find("1") == string::npos){
    return 1;
  }
  if(x[len/2] == '1'){
    return check_binary(x.substr(0,len/2)) && check_binary(x.substr(len/2 + 1)); 
  }
  else{
    return 0;
  }
}

vector<int> solution(vector<long long> numbers) {
  vector<int> answer;
  for(auto number: numbers){
    string bn ="";
    while(number >0){
      if(number % 2 == 1)
        bn += "1";
      else
        bn += "0";
      number /= 2;
    }
    bn = fillDummy(bn);
    answer.push_back(check_binary(bn));
  }
  return answer;
}

 

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