[프로그래머스 Level.3] 표현 가능한 이진트리 (2023 KAKAO BLIND RECRUITMENT) (Java)

문제 링크

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

프로그래머스

 

 

 

 

코딩테스트 연습 > 2023 KAKAO BLIND RECRUITMENT > 표현 가능한 이진트리

 

 

문제 설명

 

 

당신은 이진트리를 수로 표현하는 것을 좋아합니다.

 

이진트리를 수로 표현하는 방법은 다음과 같습니다.

 

1. 이진수를 저장할 빈 문자열을 생성합니다.
2. 주어진 이진트리에 더미 노드를 추가하여 포화 이진트리로 만듭니다. 루트 노드는 그대로 유지합니다.
3. 만들어진 포화 이진트리의 노드들을 가장 왼쪽 노드부터 가장 오른쪽 노드까지, 왼쪽에 있는 순서대로 살펴봅니다. 노드의 높이는 살펴보는 순서에 영향을 끼치지 않습니다.
4. 살펴본 노드가 더미 노드라면, 문자열 뒤에 0을 추가합니다. 살펴본 노드가 더미 노드가 아니라면, 문자열 뒤에 1을 추가합니다.
5. 문자열에 저장된 이진수를 십진수로 변환합니다.

 

이진트리에서 리프 노드가 아닌 노드는 자신의 왼쪽 자식이 루트인 서브트리의 노드들보다 오른쪽에 있으며, 자신의 오른쪽 자식이 루트인 서브트리의 노드들보다 왼쪽에 있다고 가정합니다.

 

다음은 이진트리를 수로 표현하는 예시입니다.

 

주어진 이진트리는 다음과 같습니다.

 

 

주어진 이진트리에 더미노드를 추가하여 포화 이진트리로 만들면 다음과 같습니다. 더미 노드는 점선으로 표시하였고, 노드 안의 수는 살펴보는 순서를 의미합니다.

 

 

노드들을 왼쪽에 있는 순서대로 살펴보며 0과 1을 생성한 문자열에 추가하면 "0111010"이 됩니다. 이 이진수를 십진수로 변환하면 58입니다.

 

당신은 수가 주어졌을때, 하나의 이진트리로 해당 수를 표현할 수 있는지 알고 싶습니다.

 

이진트리로 만들고 싶은 수를 담은 1차원 정수 배열 numbers가 주어집니다. numbers에 주어진 순서대로 하나의 이진트리로 해당 수를 표현할 수 있다면 1을, 표현할 수 없다면 0을 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요.

 

---

제한사항

• 1 ≤ numbers의 길이 ≤ 10,000
  • 1 ≤ numbers의 원소 ≤ 1015

 

---

 

입출력 예

numbers	result
[7, 42, 5]	[1, 1, 0]
[63, 111, 95]	[1, 1, 0]

 

---

입출력 예 설명

 

입출력 예 #1

 

7은 다음과 같은 이진트리로 표현할 수 있습니다.

 

 

 

42는 다음과 같은 이진트리로 표현할 수 있습니다.

 

 

 

5는 이진트리로 표현할 수 없습니다.

 

따라서, [1, 0]을 return 하면 됩니다.

 

 

 

입출력 예 #2

 

63은 다음과 같은 이진트리로 표현할 수 있습니다.

 

 

 

111은 다음과 같은 이진트리로 표현할 수 있습니다.

 

 

 

95는 이진트리로 표현할 수 없습니다.

 

따라서, [1, 1, 0]을 return 하면 됩니다.

 

 

 

 

 

나의 코드

import java.util.*;

class Solution {
    boolean flag;
    public int[] solution(long[] numbers) {
        int[] answer = new int[numbers.length];
        
        for(int i=0; i<numbers.length; i++) {
            flag = true;
            
            String binaryNumber = Long.toBinaryString(numbers[i]);
            
            int n = 1;
            while(Math.pow(2, n) - 1 < binaryNumber.length()) n++;
            
            if(Math.pow(2, n) - 1 > binaryNumber.length())
                binaryNumber = "0".repeat((int) Math.pow(2, n) - 1 - binaryNumber.length()) + binaryNumber;
            
            treeCheck(0, binaryNumber.length()-1, binaryNumber.split(""));
            
            if(flag)
                answer[i] = 1;
            else
                answer[i] = 0;
        }
        
        return answer;
    }
    
    public String treeCheck(int start, int end, String[] target) {
        if(start == end) return target[start];
        
        int mid = (start + end) / 2;
        String left = treeCheck(start, mid-1, target);
        String right = treeCheck(mid+1, end, target);
        
        if("0".equals(target[mid]) && "1".equals(left)) flag = false;
        if("0".equals(target[mid]) && "1".equals(right)) flag = false;
        
        // mid의 값인 target[mid]의 값을 리턴하여 left 또는 right에 담음 
        // (현재 레벨 left와 right의 부모였던 mid가 그 위 레벨의 left 또는 right가 됨)
        return target[mid]; 
    }
}

 

풀이

1. 포화이진트리의 노드의 개수를 확인해보면 2^n - 1이 된다. (포화이진트리의 레벨이 d라면 노드의 개수는 2^(d+1) - 1 이다.)
2. 따라서 주어진 numbers를 순회하면서 numbers[i]를 toBinuaryString() 메소드를 이용하여 String형의 이진수로 변경하여 binaryNumber에 저장하고 binaryNumber의 길이보다 같거나 큰 2^n - 1을 만족하는 n을 구한다. 
3. 이제 n을 구했으므로 binaryNumber의 길이가 2^n - 1이 될 때까지 binaryNumber 앞에 "0"을 붙여준다.
4. 그럼 포화이진트리의 노드 개수에는 맞는 binaryNumber를 구했으므로 해당 이진수 binaryNumber로 문제에 주어진 포화이진트리를 표현할 수 있는지 확인한다.
5. 조건을 확인해보면 자식노드가 1인 것이 있는데 부모노드가 0이면 문제에 주어진 이진트리를 만족하지 못한다. (자식노드가 1인 것이 있으면 부모노드는 무조건 1이어야 한다)
6. binaryNumber의 첫 인덱스 0을 start로 binaryNumber의 마지막 인덱스 binaryNumber.length() -1을 end로 하여 start + end / 2를 mid에 저장하고 재귀 호출을 이용하여 자식 노드로 쭉 내려가며 제일 하위의 left 노드와 right 노드를 확인하면서 해당 조건을 만족하는지 확인하면 된다.
7. left 노드로 내려가기 위해서는 start는 그대로하고 end에는 mid - 1을 넣어 재귀호출을 하면 해당 노드의 left 노드로 내려갈 수 있다.
8. right 노드로 내려가기 위해서는 start에 mid + 1을 넣고 end는 그대로 하여 재귀호출을 하면 해당 노드의 right 노드로 내려갈 수 있다.
9. 이렇게 left노드와 right노드를 구하고 해당 노드와 부모노드(내려오기 전 노드)인 target[mid]를 확인하여 조건을 만족하는지 확인하면 된다.
10. 이렇게 재귀호출을 이용하여 해당 이진수가 문제에 주어진 포화이진트리를 포현할 수 있는지 확인하고 표현할 수 있다면 answer[i]에 1을 저장하고 표현할 수 없다면 answer[i]에 0을 저장한다.