표현 가능한 이진트리

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

프로그래머스

 

Level 3

 

간단해보이지만 일반적인 트리 노드 구성과 달라서 시간을 초과하다 못해 랜덤 함수로 반례 찾아가며 푼 문제

문제 설명이 상당히 난해해서 이해하는데만 20분 이상 걸린 것 같다.

 

쉽게 풀어쓰면 다음과 같다. 쉬운거 맞나?

 

1. 숫자 N 개가 Long 배열에 담겨서 들어온다.

2. 숫자를 이진 수로 변환하였을 때 포화 이진 트리로 만들 수 있는지 확인해야한다. 

3. 단, 필요에 따라 더미 노드를 추가해서 포화 이진 트리로 만들 수 있다. 

4. 더미 노드는 0으로 일반 노드는 1로 간주한다. 

5. 즉, 이진수 10 이라면 앞에 0을 추가해 010 으로 변환할 수 있다. 

6. 일반 노드 간 연결만 간선으로 간주하며 더미 노드는 실제로 간선이 없는 것으로 간주한다. 

7. 따라서 더미 노드와 일반 노드로 구성된 트리가 트리의 형태를 만족하는지 확인해야한다.  

 

좀 더 쉽게 그림으로 보자.

 

 

사실 트리를 그리고 숫자를 구했다.

예시로 3838 을 들어보면 이진법으로 변형할 경우 위와 같이 12 자리 이진수가 되며, 12 의 길이를 가지는 포화 이진트리를 가질 수 없기 때문에 좌측에 0을 3개 추가해 포화 이진 트리의 크기에 맞는 2^4 - 1 로 만들어줄 수 있다. 

 

트리를 구했다면 이제 트리의 구성을 만족하는 = 중간에 끊김이 없는 지를 확인해야하는데 이때 특정 부모 노드가 더미 노드라면 이후에 단 1개라도 일반 자식 노드가 존재할 경우 트리의 연결이 끊겨 더 이상 트리가 아니게 된다.

 

따라서 우리는 모든 부모 노드를 탐색하며 위 조건을 만족하는지 확인해야한다. 

 

나의 경우 루트 노드에서 시작해 중위 순회(in-order)로 깊이 우선 탐색을 좌우 자식 노드에 진행하며 만약 부모 노드가 한 번 이라도 더미노드일 때, 하위 자식 노드 중 하나라도 일반 노드이면 해당 숫자는 조건을 만족하지 않는다고 판단하고 정답을 반환했다. 

 

public class Solution { //표현 가능한 이진트리
    static boolean isFullBinaryTree; //조건을 만족하는 이진 트리인지 구분자.
    public int[] solution(long[] numbers) { 
        int[] answer = new int[numbers.length];
        for(int idx = 0; idx < numbers.length; idx++){
            long numberDec = numbers[idx];
            String numberBin = makeFullBinaryTree(numberDec); //십진수 -> 이진수로 변경 + 포화 이진 트리 크기에 맞게 0 추가
            isFullBinaryTree = true; //구분자 초기화 -> 진행 중 이진트리가 아닐 경우 false 로 변경
            DFS(false, numberBin.length()/2, numberBin, (int)Math.floor(Math.log(numberBin.length()+1) / Math.log(2)));
            answer[idx] = isFullBinaryTree ? 1 : 0;
        }
        return answer;
    }
    public String makeFullBinaryTree(long numberDec){
        StringBuilder result = new StringBuilder(Long.toBinaryString(numberDec));
        int maxLen = (int) Math.pow(2, (int)Math.floor(Math.log(result.length()) / Math.log(2)) + 1)-1; //최소 포화 이진 트리 크기인 2^n-1
        while(result.length() < maxLen){
            result.insert(0, "0"); //포화 이진 트리 크기가 될 떄 까지 앞에 0 추가
        }
        return result.toString();
    }
    public void DFS(boolean zeroFlag, int Node, String binNum, int level){ //이전 부모 노드가 더미인지 확인하기 위한 Flag, 현재 노드, 이진수 문자열, 자식을 찾기 위한 높이
        int[] child = getChild(Node, level); //직계 자식 구하기
        zeroFlag = zeroFlag || binNum.charAt(Node) == '0'; //기존에 더미노드가 찾아져 Flag 가 true 이거나 현재 방문한 부모 노드가 0 일 경우
        if(zeroFlag){ //하위 자식 노드는 1 존재해서는 안된다
            if(binNum.charAt(child[0]) == '1' || binNum.charAt(child[1]) == '1'){
                isFullBinaryTree = false; //일반 자식 노드 발견 시 트리가 아님 -> 연결이 끊긴 트리
                return;
            }
        }
        if(child[1]-child[0] < 3){ //다음 방문할 노드가 리프 노드면 정지
            return;
        }
        DFS(zeroFlag, child[0], binNum, level-1); //왼쪽 자식 DFS
        DFS(zeroFlag, child[1], binNum, level-1); //오른쪽 자식 DFS
    }

    public int[] getChild(int parent, int parentLevel){ //직계 자식 구하는 메소드
        int maxLen = (int) Math.pow(2, parentLevel);
        int quarterLen = maxLen/4;
        return new int[]{parent-quarterLen, parent+quarterLen};
    }
}