2023 카카오 블라인드 코딩테스트 4번 표현 가능한 이진트리 / C++

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

프로그래머스

 

아이디어

받은 숫자를 포화 이진트리(2의 n승 -1)로 만들어야하고 각 부모노드를 확인하며 0인 부모노드 하위에 1인 노드가 존재하면 안된다는 것을 생각하며 dfs를 이용하여 순회하면 된다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
string convertDec2Bin(long long n) {
	string b = "";
	while (n) {
		if (n & 1)
			b += "1";
		else
			b += "0";
		n >>= 1;
	}
	reverse(b.begin(), b.end());
	return b;
}

string makeTree(string s) {
	long long k = 1;
	while (true) {
		if (s.size() <= k - 1)
			break;
		k <<= 1;
	}
	return string(k - 1 - s.length(), '0') + s;
}


bool checkTree(string& str, int left, int right) {

	if (left == right) {
		return true;
	}
	int mid = (left + right) >> 1;
	//부모노드가 0이라면 하위노드중 하나라도 1이되면 안됨
	if (str[mid] == '0') {
		for (int j = left; j <= right; j++)
			if (str[j] == '1') return false;
		return true;
	}
	return checkTree(str, left, mid - 1) & checkTree(str, mid + 1, right);
}

vector<int> solution(vector<long long> numbers) {
	vector<int> answer;
	for (auto n : numbers) {
		string strbit = makeTree(convertDec2Bin(n));
		answer.push_back(checkTree(strbit, 0, strbit.length() / 2));
	}
	return answer;
}

int main(void) {
	vector<long long> v = { 7, 42, 5 };
	solution(v);
}