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

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

프로그래머스

 처음에는 이 문제를 어떻게 접근해야할지 도저히 감을 잡을 수 없었다. 어떻게 해야 이진 트리로 표현할 수 있을지 계속 고민했었다. 그러다가 갑자기 든 생각이 있었는데, 바로 부모 노드가 더미 노드일 때 자식 노드는 존재할 수 없다는 사실을 알게 되었다. 그런데 여기서 무작정 2진법으로 표현한 수의 뒤에서 두 번째 자리의 수부터 0이 있다면 그것은 이진 트리로 나타낼 수 없을 것이라 단순하게 생각했고, 계속 틀렸었다.

잘못 이해했던 것을 표현한 그림. 빨간 밑줄 부분이 0이 되면 안된다고 생각했었다.

 그러다, 도저히 안 풀려서 내가 문제를 제대로 이해하기는 했나 싶어서 이 문제의 질문들을 보았고, 여기에서 힌트(사실상 해답)를 얻어서 이 문제를 풀 수 있었다. 일단, 문제의 상황을 잘못 이해했음을 깨달았고, 이를 기반으로 코드를 작성하였다. 코드의 흐름은 다음과 같다.

1. (주어진 numbers 중 하나를 기준으로) 이 수를 2진법으로 나타낸 수를 구한다.
2. 만약 이 수의 (0, 1로 이루어진 문자열의) 길이가 딱 포화 이진 트리의 노드 개수(2^높이 - 1)와 일치하지 않는다면, 가장 작은 값의 높이에 따른 노드의 개수를 구한다.
3. 이 높이의 수와 일치하게, 미리 구한 2진수의 앞에 0을 붙인다. (만약 구한 수가 1111이라면, 길이가 7이 되게 0001111로 만든다)
4. 만약 부모 노드의 값이 0이라면 (더미 노드라면) 자식 노드는 절대 1이 될 수 없다.(자식 노드도 더미 노드이어야 한다.)
5. 4번의 과정을 재귀를 통해 체크하고, 만약 해당 2진수가 문제의 조건에 부합하면 answer에 1을, 부합하지 않는다면 answer에 0을 넣는다.

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

string number;

// 10진수를 2진수로 바꾸는 함수
string DecToBin(long long number)
{
	string result = "";

	while (number > 0)
	{
		number % 2 == 1 ? result += '1' : result += '0';
		number /= 2;
	}

	reverse(result.begin(), result.end());

	return result;
}

// 적절한 노드의 개수를 구하는 함수
int NodeNum(string number)
{
	if (number.size() == 1)
		return 1;

	int len = 2;
	int currentNodeNum = number.size();
	int befNodeNum = 1;

	while (true)
	{
		int nodeNum = pow(2, len) - 1;

		if (befNodeNum < currentNodeNum && currentNodeNum <= nodeNum)
			return nodeNum;

		++len;
		befNodeNum = nodeNum;
	}
}

bool Check(int start, int end)
{
	// 만약 start와 end의 차가 1이라면, 자식 노드를 체크하는 중이라는 뜻이므로 true를 반환
	if (end - start == 1)
		return true;

	// 부모 노드는 가운데에 위치한다.
	int parentIdx = (start + end) / 2;

	// 만약 부모 노드가 0이라면 (더미 노드라면), 자식 노드는 절대 1일 수가 없다. 
	if (number[parentIdx] == '0')
	{	
		// 각각 왼쪽 자식 노드의 번호와 오른족 자식 노드의 번호를 구한다. 
		int leftChildIdx = (start + parentIdx) / 2;
		int rightChildIdx = (parentIdx + 1 + end) / 2;

		// 만약 둘 중 하나라도 값이 1이라면 (더미 노드가 아닌게 있다면), 이것은 존재할 수 없으므로 false를 반환한다.
		if (number[leftChildIdx] == '1' || number[rightChildIdx] == '1')
			return false;
	}

	// 부모 노드를 기준으로 왼쪽과 오른쪽의 결과를 and 연산한 것을 반환한다. (하나라도 불가능한 경우가 있으면 안되기 때문)
	return Check(start, parentIdx) && Check(parentIdx + 1, end);
}

vector<int> solution(vector<long long> numbers) {
	vector<int> answer;

	for (int i = 0; i < numbers.size(); ++i)
	{
		number = DecToBin(numbers[i]);
		
		int nodeNum = NodeNum(number);

		while (number.size() < nodeNum)
			number = "0" + number;
	
		bool success = Check(0, number.size());

		if (success)
			answer.push_back(1);
		else
			answer.push_back(0);
	}

	return answer;
}

 

 

---

참고: https://school.programmers.co.kr/questions/42319