[Programmers] 표현 가능한 이진트리

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/150367

프로그래머스

 

해당 문제의 핵심은 서브 트리 내 루트가 반드시 1이어야 한다는 점입니다.

 

알고리즘은 다음과 같습니다.

1. 주어진 십진수를 이진수로 변환한 뒤 포화이진트리 형태가 아니라면 포화이진트리 형태가 되도록 0을 추가해 줍니다.

2. 1번에서 구한 이진수의 가운데를 시작으로 모든 서브 트리 내 루트 노드가 존재하는지 확인합니다.

2.1 2번 조건이 성립하면 1, 성립하지 않으면 0을 answer 벡터에 추가합니다.

3. 주어진 numbers 배열 내 모든 원소에 대해 1 ~ 2번 과정을 반복하고 answer 벡터를 반환합니다.

 

	#include <string>
	#include <vector>
	#include <algorithm>
	#include <iostream>
	using namespace std;
	bool allZero(string binary)
	{
	for (char c : binary)
	{
	if (c != '0')
	{
	return false;
	}
	}
	return true;
	}
	string convert(long long number)
	{
	string binary = "";
	while (number)
	{
	binary = to_string(number % 2) + binary;
	number /= 2;
	}
	int idx = 1;
	int len = binary.length();
	while (len >= (1 << idx))
	{
	idx++;
	}
	for (int i = 0; i < (1 << idx) - len - 1; i++)
	{
	binary = "0" + binary;
	}
	return binary;
	}
	bool check(string binary)
	{
	if (binary.length() == 1
	|| allZero(binary))
	{
	return true;
	}
	int root = binary.length() / 2;
	string leftSubTree = binary.substr(0, root);
	string rightSubTree = binary.substr(root + 1);
	return (binary[root] == '1'
	&& check(leftSubTree)
	&& check(rightSubTree));
	}
	vector<int> solution(vector<long long> numbers) {
	vector<int> answer;
	for (long long number : numbers)
	{
	string binary = convert(number);
	answer.push_back(check(binary));
	}
	return answer;
	}

view raw .cpp hosted with ❤ by GitHub

 

 

개발환경: Programmers IDE  

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~