코딩 테스트
[프로그래머스] 표현 가능한 이진 트리 자바
한 면만 쓴 종이
2025. 3. 19. 20:41
https://school.programmers.co.kr/learn/courses/30/lessons/150367
분할정복을 사용하는 문제입니다.
[풀이한 코드]
import java.util.*;
class Solution {
public int[] solution(long[] numbers) {
int[] answer = new int[numbers.length];
for (int i = 0; i < numbers.length; i++) {
answer[i] = getAnswer(numbers[i]);
}
return answer;
}
static int getAnswer(long number) {
// 1) 십진수 -> 이진수 변환
String binary = Long.toBinaryString(number);
// 2) 이진수에 더미 노드 채우기
double size = getSize(binary.length());
StringBuilder add = new StringBuilder();
for (int i = binary.length(); i < size; i++) {
add.append("0");
}
binary = add.toString() + binary;
// 3) 만든 트리가 올바른 트리인지 확인하기
if (isBinaryTree(binary)) {
return 1;
}
return 0;
}
static int getSize(int length) {
int h = 1;
while((int) Math.pow(2, h) - 1 < length) {
h++;
}
return (int) Math.pow(2, h) - 1;
}
static boolean isBinaryTree(String tree) {
int len = tree.length();
if (tree.length() == 0) {
return true;
}
int root = len / 2;
String leftSubTree = tree.substring(0, root);
String rightSubTree = tree.substring(root + 1);
if (tree.charAt(root) == '0') {
return isZeroTree(tree.substring(0, root)) && isZeroTree(tree.substring(root + 1));
}
return isBinaryTree(leftSubTree) && isBinaryTree(rightSubTree);
}
static boolean isZeroTree(String tree) {
int len = tree.length();
if (tree.length() == 0) return true;
int root = len / 2;
String leftSubTree = tree.substring(0, root);
String rightSubTree = tree.substring(root + 1);
if (tree.charAt(root) == '1') {
return false;
}
return isZeroTree(leftSubTree) && isZeroTree(rightSubTree);
}
}
[기억하자]
1. 포화 이진 트리의 노드 수: 2 ^ (h + 1)) - 1
- 루트 노드의 레벨을 0이라고 생각했을 때의 공식이다.
- 루트 노드의 레벨을 1이라고 생각하면 2 ^ h - 1 이다.
- 자바로 하면, (int) Math.pow(2, h) - 1 < length 이다. Math.pow() 의 반환값은 double 이기 때문에 (int) 로 강제 형변환할 수 있다.
2. Long.toBinaryString(num)
- Integer.toBinaryString(num)도 가능하다.
- 이진수로 변환해준다.
3. String.substring(int st, int en)
- string의 s는 대문자가 아니라 소문자이다!
4. 트리에서 분할정복 방법
- 트리를 오른쪽 트리와 왼쪽 트리로 나눈다.
- 왼쪽 트리와 오른쪽 트리를 재귀함수로 다시 넣어서 반복한다.
private static boolean dfs(String number) {
boolean valid = true;
int mid = (number.length()-1)/2;
char root = number.charAt(mid);
String left = number.substring(0,mid);
String right = number.substring(mid+1,number.length());
if(root == '0' && (left.charAt((left.length()-1)/2)=='1' || right.charAt((right.length()-1)/2)=='1')){
return false;
}
valid = dfs(left);
if (valid) {
valid = dfs(right);
}
if(left.length() >= 3) { // 리프노드는 0이어도 상관없기 때문에 길이가 3이상일 때만 탐색
valid = dfs(left);
if(valid) {
valid = dfs(right);
}
}
return valid;
}