표현가능한 이진트리

 

이번 코딩테스트의 전체적인 요구사항은 long타입의 넘버를 담은 배열의 각 수들을 이진수로 변환후 포화 이진트리로 만들어 해당 숫자가 이진트리로 표현이 가능한가를 구해내야된다.

 

해당 테스트를 완료하는데 4시간 소요됨

(문제 본문, 프로그래머스 : https://school.programmers.co.kr/learn/courses/30/lessons/150367 ) 

 

 

리스트와 재귀를 이용

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];//결과값을 담는 배열
        
        for(int i =0; i<numbers.length; i++){
            LinkedList<String> treeList = perfactBinaryTree(numbers[i]);// 1.각 수의 포화이진트리를 구함
            answer[i] = checkAble(treeList);// 2.해당 포함 이진트리가 표현이 가능한지 증명
        }


        return answer;
    }
    
    LinkedList<String> perfactBinaryTree(long num){// 1번 
        LinkedList<String> orignalTree = new LinkedList<>(Arrays.asList(Long.toBinaryString(num).split("")));
		// 배열안의 싱글넘버를 매개변수로 전달받아 이진수로 변환한후 리스트에 담음
        
        int maxLength=0; // 포화 이진트리의 규모를 측정하는 반복문
        while (orignalTree.size()> maxLength){
            maxLength = (maxLength*2)+1;
        }  // 포화이진트리는 0(혹은 1)부터 시작하여 2n+1의 노드수를 가지고있다.
        
        while(orignalTree.size()< maxLength){
            orignalTree.add(0,"0");
        }// 포화 이진트리의 규모에 마춰서 리스트 설계
        
        return orignalTree; // 포화 이진트리가 완성된 리스트 반환
    }

    int checkAble(List treeList){ // 2번, 완성된 포화 이진트리를 가진 리스트를 매개변수로 받음
        if(treeList.size()==1) return 1;

        int myNodeIndex = treeList.size()/2;
        int gapToChildIndex = (treeList.size()+1)/4;//트리 규모에 의해 내 위치를 기준으로 자식노드의 위치가 달라짐
        int leftChildIndex = myNodeIndex - gapToChildIndex;
        int rightChildIndex = myNodeIndex + gapToChildIndex;
		//내 위치의 인덱스와 자식노드 위치의 인덱스를 구함 

		//여기서부터 재귀를 실행하며 조건에 따라 트리로 표현이 가능한 이진수인지를 판별
        // 숫자 0과 1은 트리구조의 가능성, 즉 true와 false 역활
        if(checkAble(treeList.subList(0,myNodeIndex))==0) return 0;
        else if(checkAble(treeList.subList(myNodeIndex+1,treeList.size()))==0) return 0;
		
        // String "0"과 "1"은 트리안의 자신의 노드의 존재 유무를 표현
        if(treeList.get(myNodeIndex).equals("0") && 
        (treeList.get(leftChildIndex).equals("1") || 
        treeList.get(rightChildIndex).equals("1")))
            return 0;

        return 1;
    }
}

 

2번, checkAble()메서드에서 해당 트리가 트리형태를 가지고 있는지 구하는 조건은 딱 한가지이다.

 

위의 그림과 같이 자식노드가 존재하지만 자신의 노드가 더미노드, 즉 존재하지 않을 경우에 트리형태가 될수 없으며 위와 같은 형태의 이진수를 찾는것이 이번 코딩테스트의 핵심이다. 

 

재귀를 돌며 leaf노드부터 1, 2, 3번 노드와 같은 형태를 찾으며 하위 노드들중 해당 형태가 존재할경우 0을 리턴하도록 하였다.

 

 

마무리

사실 막상 코드를 완성하고 나니 쉬운문제였다.  또한 문제의 내용과 다르게 이진트리를 만들필요 조차없었으며(문제를 풀기위해 이진트리에 대한지식은 필요했지만...) 오히려 이진수를 이진트리로 비쥬얼화 하면서 문제가 더 복잡하게 느껴졌고 코드 작성중 제일 시간이 많이 소요된 부분이었다.

 

이진트리와 이진수가 매칭이 잘 안됬으며 그런 상태에서 서로의 상관관계(포화 이진트리를 이진수로 표현한다든지 루트부터 시작해 자식노드들을 구하는 식들)을 구하는 부분이 어려웠다.