문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/150367
[이 문제는 프로그래머스에서 푼 문제입니다.]
이 문제는 문제의 조건을 재귀함수를 이용하여 탐색하여 풀 수 있습니다. 문제에서 구현해야 하는 부분은 크게 2가지 입니다.
- 현재 수(10진수)를 포화 이진 트리로 치환 가능한 이진수로 변경하기
- 구한 이진수가 포화 이진 트리로 치환 가능한지 체크하기
첫 번째 부분의 경우는 포화 이진 트리의 특징을 이용하여 진행할 수 있습니다. 포화 이진 트리의 크기는 2^n - 1 이기 때문에 주어진 수를 이진수로 변환했을 때 자리수가 더 커질 때까지 n값을 증가시킵니다. 그 후 이진수의 길이와 포화 이진 트리의 크기가 같아질 때까지 이진수의 앞에 0을 추가합니다.
두 번째 부분 역시 포화 이진 트리의 특징을 이용하여 진행할 수 있습니다. 루트 노드의 경우 문자열 길이의 가운데에 위치해있는 것을 알 수 있습니다. 이 때 루트 노드에서 비교할 자식 노드들은 다시 자식 노드를 이루고 있는 문자열의 가운데에 위치해있습니다. 따라서 루트 노드와 각각 왼쪽과 오른쪽 두 개의 서브 노드끼리 비교합니다. 이 때 루트 노드가 0인데 자식 노드가 1일 경우 성립할 수 없으므로 false를 리턴, 그 외의 경우는 자식 노드의 문자열 길이가 3보다 작아질 때까지 재귀함수로 계속 절반씩 나누어 비교하는 방식으로 진행합니다.
여기서 제약 조건을 다시 살펴보겠습니다. 각 원소의 크기는 10^15 이하입니다. 위의 로직대로라면 주의해서 보아야 할 것은 자리수이기 때문에, 10^15 < 16^15 = 2^60, 즉 자리수는 대략 계산해보아도 60자리를 넘지 않기 때문에 자리수 값은 int로 설정 가능합니다.
코드를 보여드리기 전에 하나 의문점이 있어 이 부분은 조금 더 공부해보려고 합니다. 왼쪽의 자식 노드의 값과 오른쪽의 자식 노드의 값을 char로 저장한 후 실행하면 런타임 에러가 나타나는데, 이 부분을 저장하지 않고 if문 내부에 그대로 사용할 경우 통과되는 것을 확인하였습니다. 이 부분의 원인이 무엇인지 조금 더 살펴봐야 할 것 같습니다.
다음은 코드입니다.
class Solution {
static boolean isValidNum(String binary){
// 루트 노드의 경우 문자열 길이의 한 가운데
int mid = (binary.length()-1)/2;
char root = binary.charAt(mid);
// 루트 노드의 자식 노드는 가운데 기준 왼쪽 수의 가운데 수와 오른쪽 수의 가운데 수
String left = binary.substring(0,mid);
// char leftSubRoot = left.charAt((left.length()-1)/2);
String right = binary.substring(mid+1,binary.length());
// char rightSubRoot = right.charAt((right.length()-1)/2);
// 루트 노드는 0인데 자식 노드가 1일 경우는 false
// if(root=='0' && (leftSubRoot=='1' || rightSubRoot=='1')) return false;
if(root=='0' && (left.charAt((left.length()-1)/2)=='1' || right.charAt((right.length()-1)/2)=='1')) return false;
// 그 외의 경우는 왼쪽 수와 오른쪽 수를 재귀 실행
// 이 때 왼쪽 수의 크기가 3보다 작을 경우 리프 노드에 도달했으므로 비교하지 않음
boolean result = true;
if(left.length() >= 3){
// 왼쪽 실행 결과가 true라면 오른쪽 실행
result = isValidNum(left);
if(result) result = isValidNum(right);
}
// 오른쪽 실행 결과 리턴
return result;
}
public int[] solution(long[] numbers) {
int[] answer = new int[numbers.length];
// 포화 이진 트리 만들기
for(int i=0;i<numbers.length;i++){
// 1. 현재 수를 이진수로 변환
String binary = Long.toBinaryString(numbers[i]);
// 2. 포화 이진 트리의 크기는 2^n - 1 이기 때문에 현재 구한 이진수의 n값을 구하기
int exponent = 0;
while((int)Math.pow(2,exponent)-1 < binary.length()){
exponent++;
}
// 3. 현재 길이와 포화 이진 트리의 크기와 다르다면 앞에 0 추가
while((int)Math.pow(2,exponent)-1 != binary.length()){
binary = "0" + binary;
}
// 만약 이진수가 포화 이진 트리로 표현 가능하다면 answer에 1 추가
if(isValidNum(binary)) answer[i] = 1;
else answer[i] = 0;
}
return answer;
}
}
