이진트리
프로그래머스 2023 KAKAO BLIND RECRUITMENT Level 2 문제 표현 가능한 이진트리를 java를 이용하여 풀어보았다.
다른 풀이들을 살펴볼 때 생략된 내용만 간단히 적어보자.
문제 링크 첨부한다.
https://school.programmers.co.kr/learn/courses/30/lessons/150367
연결 가능성
문제의 핵심은 다음과 같다.
2진수로 표현했을 때 얻게되는 문자 배열들이 하나의 연결된 이진트리로 표현 가능한가?
이를 위해 0과 1로 이루어진 배열이 하나의 연결된 이진트리인지 어떻게 확인할 것인가에 대해 고민해야 한다.
부모와 자식
부모가 없으면 자식도 없어야 한다. 하지만 부모가 있다면 자식은 하나만 있어도 되고 둘 다 있어도 되고 하나도 없어도 된다. 이를 그림으로 표현하면 다음과 같다.
위의 그림은 부모가 있을 경우다. 부모는 문제의 경우 1로 처리하게 되는 것이다. 하지만 부모가 없다는 의미의 0이 온다면?
부모가 없다는 의미의 0이 오게 되면 당연히 자식도 없어야 한다. 즉 0의 자식 노드로서 1이 오면 모순인 것이다.
이를 이제 문제의 경우에 대입해 0과 1로 바꿔보자. 문제의 조건대로 포화 이진 트리를 만들어둔 상태만 고려한 케이스를 그린 것이다.
위 그림에서 얻을 수 있는 결론은 이것이다. 1의 자식 노드는 어떤 경우가 와도 상관이 없다. 하지만 0의 자식 노드는 존재하지 않거나 모두 0이어야만 한다는 사실이다. 이것을 반드시 검증해주어야 한다.
0의 자식 노드는 존재하지 않거나, 반드시 0이 와야 한다.
이 작업을 root 노드를 기준으로 재귀적으로 왼쪽 sub tree와 오른쪽 sub tree에 대해서 계속 진행하면 되는 것이다.
이진트리 판별
위에서 설명한 작업들을 코드로 구현하면 다음과 같다.
Boolean isBinaryTree(String s) {
if(s.length()==1) return true;
char mid = s.charAt(s.length() / 2);
String left = s.substring(0, s.length() / 2);
String right = s.substring(s.length() / 2 + 1);
if(mid=='0' && (left.charAt(left.length()/2)=='1' || right.charAt(right.length()/2)=='1')) return false;
return isBinaryTree(left) && isBinaryTree(right);
}if문을 보면 0의 자식 노드를 판별하는 작업을 하고 있음을 확인할 수 있다.
부모의 자식은 어디에?
처음 내가 실수했던 부분은 현재 판별하고 있는 트리의 root 노드의 자식 노드 위치를 root 노드 바로 좌우에 있는 노드들로 착각한 것이다.
굳이 따지자면 root 노드의 바로 좌우에 있는 노드들이 자식 노드이기 위해서는 재귀의 가장 마지막 step이다. length가 3인 배열을 확인하고 있을 때는 root의 바로 양옆이 자식 노드일 것이기 때문이다.
이 부분을 착각해서 재귀의 마지막 step만 검증하는 코드를 제출했다가 1번 test case 빼고 다 틀렸다.
위 코드의 if문을 통해서 부모의 자식이 어디에 있는지 확인할 수 있다.
left.charAt(left.length()/2) 와 right.charAt(right.length()/2)가 무슨 의미인지 좀 더 직관적으로 설명해보자.
전체 트리의 Root 노드의 자식 노드는 각각 Left Sub Tree의 Root와 Right Sub Tree의 Root임을 알 수 있다. 노란 형광펜으로 표시된 녀석들이다.
내가 착각한 부분은 얼핏 전체 Root의 좌우에 있다고 그림상으로 착각해서 Root의 index 로부터 +1, -1을 해서 자식 노드들의 위치값을 준 것이었다.
하지만 전체 Root의 index 값에 +1, -1을 하게 되면 노란 형광펜칠 된 노드들이 아닌 저기 밑에 있는 노드들을 가리키게 된다.
즉, 내가 처음 잘못 작성한 코드의 if문을 의미만 통하게 작성해보자면 다음과 같았다.
if(mid=='0' && ((mid-1)=='1' || (mid+1)=='1')) return false;하지만 이게 아니라 자식 노드들을 정확하게 가리키기 위해서는 left sub tree와 right sub tree의 root 로 접근해주어야 한다.
if(mid=='0' && (leftSubTree.mid=='1' || rightSubTree.mid=='1')) return false;잘 이해가 됐길 바라며... 내가 제출한 코드는 다음과 같다.
import java.util.Arrays;
public class 표현가능한이진트리 {
static public int[] solution(long[] numbers) {
int[] answer = new int[numbers.length];
for(int i = 0; i < numbers.length; i++) {
String cur = Long.toBinaryString(numbers[i]);
int j = 0;
while((int)Math.pow(2, j)-1 < cur.length()) {
j++;
}
while((int)Math.pow(2, j)-1 != cur.length()) {
cur = "0"+ cur;
}
if(isBinaryTree(cur)) {
answer[i] = 1;
}
}
return answer;
}
static Boolean isBinaryTree(String s) {
if(s.length()==1) return true;
char mid = s.charAt(s.length() / 2);
String left = s.substring(0, s.length() / 2);
String right = s.substring(s.length() / 2 + 1);
if(mid=='0' && (left.charAt(left.length()/2)=='1' || right.charAt(right.length()/2)=='1')) return false;
return isBinaryTree(left) && isBinaryTree(right);
}
}마치며
이진트리를 구현하여 푸는 문제는 아니지만 개념에 대해 제대로 이해하고 있지 않으면 내가 설명한 부분의 풀이를 떠올릴 수 없었을 것 같다. 자료구조에 대한 단순한 지식이 아니라, 그 원리에 대해 깊게 이해하고 있어야 이런 문제들을 빠르게 풀 수 있겠다.
