[코테연습] 869. Reordered Power of 2

- 정렬문제

 

https://leetcode.com/problems/reordered-power-of-2/description/

 

- 해결방법

 

1. n 으로 만들 수 있는 숫자를 구한다.
 1-1. 2 의 배수인지 확인한다. ( x % 2 == 0 )
2. 거듭제곱인지 확인한다.
 2-1. 나머지가 1 경우, true
 2-2. 2 로 나누면서 확인한다.

 

class Solution {
    List<Integer> list;
    public boolean reorderedPowerOf2(int n) {
        list = new ArrayList<>();
        String str = String.valueOf(n);
        String[] arr = str.split("");

        int size = arr.length;
        dfs(arr, size, 0, new boolean[size], 0, new String[size]);
        
        boolean found = false;
        for (int num : list) {
            while(!found) {
                if (num == 1) {
                    found = true;
                    break;
                }
                num/=2;
                if (num % 2 != 0) {
                    if (num == 1) {
                        found = true;
                        break;
                    }
                    break;
                }
            }
        }
        return found;
    } 
    void dfs(String[] arr, int n, int depth, boolean[] visited, int start, String[] output) {

        if ( depth == n) {
            if (output[0].equals("0")) return;
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < output.length; i++) {
                sb.append(output[i]);
            }
            int number = Integer.parseInt(sb.toString());
            if (number != 1 && number % 2 != 0) return;
            list.add(number);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                output[depth] = arr[i];
                dfs(arr, n, depth+1, visited, start, output);
                visited[i] = false;
            }
        }

    }

}