[LeetCode] 869. Reordered Power of 2 / JAVA

문제 설명 보기

leetcode.com/problems/reordered-power-of-2/

> Desc

입력된 숫자의 자리를 자유롭게 교체해 2의 제곱 승 꼴의 숫자로 만들수 있는지 물어보는 문제다.

 

>IDEA

1. 숫자의 위치를 자유롭게 바꾼다.

순열 (Permutation)

2. 2의 제곱 승 꼴의 숫자

비트연산자 활용

 

>Solution(Permutation)

class Solution {
    boolean permutation(String prefix, String str){
        if(str.length() == 0) {
            if ((Integer.parseInt(prefix) | Integer.highestOneBit((Integer.parseInt(prefix))) )== Integer.highestOneBit((Integer.parseInt(prefix)))) return true;
        }
        for(int idx = 0; idx < str.length(); idx++){
            if (!prefix.startsWith("0")) {
                if (permutation(prefix + str.charAt(idx), str.substring(0, idx) + str.substring(idx + 1)))
                    return true;
            }
        }
        return false;
    }

    public boolean reorderedPowerOf2(int N) {
        String str = String.valueOf(N);
        return permutation("", str);

    }
}

 

> Result

 

대충 어떻게 시간초과를 면했는지 모르겠다.

 

그래서 모범답안을 컨닝해봤다.

 

class Solution {
    public boolean reorderedPowerOf2(int N) {
        int[] A = count(N);
        for (int i = 0; i < 31; ++i)
            if (Arrays.equals(A, count(1 << i)))
                return true;
        return false;
    }

    // Returns the count of digits of N
    // Eg. N = 112223334, returns [0,2,3,3,1,0,0,0,0,0]
    public int[] count(int N) {
        int[] ans = new int[10];
        while (N > 0) {
            ans[N % 10]++;
            N /= 10;
        }
        return ans;
    }
}

 

2의 제곱승 꼴의 숫자를 10진수로 표현했을 경우, 사용된 각 자릿수의 숫자의 개수를 세어 비교한다.