[프로그래머스][Java] 택배 배달과 수거하기 (268)

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

프로그래머스

생각의 흐름

이문제를 보고 생각한 방식은 다음과 같았다.

1) 일단 10진수를 2진수로 변환한다

2) 변환된 2진수를 재귀적으로 (왼쪽, 중심, 오른쪽) 으로 나누어서 탐색하면서 판단하면 되겠다! 였다!

 

하지만 생각하지 못했던 부분이 있었는데, 10진수를 2진수로 변환한다고 끝나는 것 이 아니다...

변환된 2진수가 만약 포화 이진트리가 아니라면 비트열 맨 앞에 0을 추가해주어야 한다.

 

문제에서 주어진 input을 생각해봅시다.

7 = 111 (O)

42 = 0101010 (O)

5 = 101 (X)

 

규칙이 조금씩 보이시나요?

읽는 순서를 고려했을 때, 루트노드는 항상 2진수의 중앙에 옵니다.

루트노드에 더미노드(0)이 올 수 있을까요? 없습니다. 루트노드가 0인 수는 0뿐인데, 주어지는 숫자는 1이상 이기 때문입니다.

따라서, 규칙 하나를 찾았습니다. '2진수의 중앙은 0이 될 수 없다.'

 

조금 확장해서 생각해보면, root가 0인 substree의 양쪽 자식들은 1이될 수 없습니다.

0이라는 것은 더미 노드이기 때문에, 자식이 있을 수 없기 때문이죠!

 

▶ 분할정복 

이제 위에서 살펴본 내용을 바탕으로 분할정복 하는것이 중요합니다. 다음 예시를 생각해봅시다.

110 = 1101111

(1) 분할시작

110(왼쪽 서브트리) / 1(부모) / 111(오른쪽 서브트리) 로 분할합니다.

이후 왼쪽과 오른쪽을 정복한 후 이진트리로 표현할 수 있는지 판단합니다.

 

(1 - 2) 부모가 1인 경우

일단 이진트리로 표현할 가능성이 있습니다.

왼쪽과 오른쪽 서브트리 또한 이진트리로 표현할 수 있다면, 비로소 이진트리로 표현할 수 있습니다.

 

(1 - 3) 부모가 0인 경우

부모가 0인 경우는 모두 불가능할까요? 아닙니다.

부모가 0이면서 자식도 모두 0이면 가능한 case가 됩니다. 이를 함수 isAllZero()로 해결할 수 있습니다.

 

나의 코드

import java.util.*;

class Solution {
    public int[] solution(long[] numbers) {
        int[] answer = new int[numbers.length];

        for(int i = 0; i < numbers.length; i++) {
            String numStr = covertBinary(numbers[i]);
            
            if(check(numStr, 0, numStr.length() - 1)) {
                answer[i] = 1;
            } else {
                answer[i] = 0;
            }
        }

        return answer;
    }
    
    public boolean check(String numStr, int start, int end) {
        if (isAllZero(numStr, start, end) || end - start == 1) return true;
        
        int mid = (start + end) / 2;
        if(numStr.charAt(mid) == '1' && check(numStr, start, mid - 1) && check(numStr, mid + 1, end)) {
            return true;
        } else {
            return false;
        }
    }
    
    boolean isAllZero(String str, int l, int r) {
        for (; l <= r; l++) {
            if (str.charAt(l) != '0') return false;
        }
        return true;
    }
    
    public String covertBinary(long num) {
        StringBuilder sb = new StringBuilder();
        
        while(num > 0) {
            long b = num % 2;
            sb.append(b);
            num /= 2;
        }
        
        int idx = 2;
        int len = sb.length();
        while (true) {
            if (len <= idx - 1) break;
            idx *= 2;
        }
        for(int i = 0; i < idx - 1 - len; i++) {
            sb.append(0);
        }
        
        return sb.reverse().toString();
    }
}