[프로그래머스, Lv.3] 표현가능한 이진트리 (java)

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

프로그래머스

728x90

---

메모리: 95.9 MB

시간: 52.17 ms

 

와... 맨날 ide에서 개발하다가 프로그래머스로 문제 풀면 쉬운 문제도 풀기 힘든데, 이번 문제는 진짜 어려웠다.

일단 문제 이해부터 잘 못해서 두, 세번 코드 거의 갈아엎었다.

 

1. numbers 안의 long 타입 변수들 for문으로 하나하나 접근하며 답을 구한다. (numbers[i]를 n에 저장)
2. n이 1이면 무조건 노드가 1개인 이진트리로 표현할 수 있기 때문에 답에 1을 저장하고 다음 답을 구하러 넘어간다.
3. n을 이진수 몇 자리로 표현 가능한지 구해주고 이를 cnt에 담는다. (ex. 58는 이진수로 111010이므로 6자리 표현 가능, cnt = 6)
4. n을 포화이진트리로 만드려면 몇 자리로 표현해야 하는지 구해준다. 포화 이진트리는 $2^N - 1$개의 노드를 가지고 있으므로 cnt보다 큰 $2^N$ 중 가장 작은 수를 구하면 된다. 이를 leng에 저장해준다. (cnt = 6일 때, 포화이진트리로 표현하기 위해서는 노드가 $2^3 - 1$개 필요하므로 leng은 $2^3$)
5. 각 leng 크기의 배열을 하나 선언해서 n을 이진수로 표현하여 각 자리에 잘 넣어준다. (ex. n = 58, 이진수로 표현하면 111010, 포화이진트리 형식으로 표현하기 위해서는 $2^3-1$로 표현해야 하므로 0111010, 이를 배열에 저장하면 [ 0, 1, 1, 1, 0, 1, 0], 이배열을 밑의 그림처럼 나타낼 수 있다.)
6. 밑의 그림을 보면 알겠지만, 각 depth의 가장 왼쪽에 있는 노드는 항상 $2^N$이고, 해당 depth에 있는 노드들은 자신의 자식에 접근하려면 $2^{N - 1}$을 +, - 하면 된다.
7. 위의 방법으로 자식 노드들에 접근하며 표현 가능한지 확인해준다. 현재 노드가 0일 때 자식 노드가 1이라면 표현 불가능한 이진트리가 된다. 또한 자식 노드와 인덱스가 1 차이 밖에 나지 않는다면, 자식 노드는 리프 노드이므로 더 이상 검사해주지 않아도 된다.

import java.util.*;

class Solution {
    public int[] solution(long[] numbers) {
        int[] answer = new int[numbers.length];
        
        for(int i = 0; i < numbers.length; i++) {
            long n = numbers[i];
            
            if(n == 1) { // n이 1이면 아래의 과정을 거치지 않고 바로 다음 답 확인하러
                answer[i] = 1;
                continue;
            }
            
            // n을 이진수 몇 자리 수로 표현 가능한지 구하기
            long temp = 1;
            int cnt = 0;
            while(n >= temp) {
                temp *= 2;
                cnt++;
            }
            
            // 포화이진트리를 만드려면 몇 자리 수로 표현해야 하는지 구하기
            int leng = 1;
            while(cnt >= leng) {
                leng *= 2;
            }

            // 이진수로 표현한 n을 각 자리 수에 맞게 넣기
            int[] node = new int[leng];
            for(int j = 1; j <= leng - 1 - cnt; j++) node[j] = 0; // 포화이진트리를 만들기 위해 추가한 0
            for(int j = leng - 1; j > leng - 1 - cnt; j--) {
                node[j] = (int)(n % 2);
                n /= 2;
            }
            
            
            // 루트노드부터 밑으로 내려가면서 부모 노드가 0이 아닌지 확인
            Queue<int[]> q = new LinkedList<>();
            q.add(new int[] {(leng + 1) / 2, (leng + 1) / 4}); // 현재 노드 번호(지금은 root)와 자식 노드와의 차이
            
            boolean result = true;
            while(!q.isEmpty()) {
                int[] now = q.poll();
                
                if(node[now[0]] == 1) { // 현재가 1이면 자식이 있던 없던 상관없음.
                    if(now[1] != 1) { // 자식 노드와 차이가 1이면 자식 노드는 리프 노드이므로 확인할 필요 없음
                        q.add(new int[] {now[0] - now[1], now[1] / 2}); // 왼쪽 노드
                        q.add(new int[] {now[0] + now[1], now[1] / 2}); // 오른쪽 노드
                    }
                }
                else { // 현재가 0이면 자식이 있으면 안됨.
                    if(node[now[0] - now[1]] == 1 || node[now[0] + now[1]] == 1) { // 자식이 있다면
                        result = false; // 이진트리로 표현 불가능
                        break;
                    }
                    else {
                        if(now[1] != 1) { // 자식 노드와 차이가 1이면 자식 노드는 리프 노드이므로 확인할 필요 없음
                            q.add(new int[] {now[0] - now[1], now[1] / 2}); // 왼쪽 노드
                            q.add(new int[] {now[0] + now[1], now[1] / 2}); // 오른쪽 노드
                        }
                    }
                }
            }
            
            if(result) answer[i] = 1;
            else answer[i] = 0;
            System.out.println();
        }
        
        return answer;
    }
}