문제 설명 보기
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진수로 표현했을 경우, 사용된 각 자릿수의 숫자의 개수를 세어 비교한다.
'Algorithms > LeetCode DailyChallenge' 카테고리의 다른 글
[LeetCode] 423. Reconstruct Original Digits from English / JAVA (0) | 2021.03.29 |
---|---|
[LeetCode] 966. Vowel Spellchecker / JAVA (0) | 2021.03.23 |
[LeetCode] 841. Keys and Rooms / JAVA (0) | 2021.03.20 |
[LeetCode] 376. Wiggle Subsequence / JAVA (0) | 2021.03.18 |
[LeetCode] 714. Best Time to Buy and Sell Stock with Transaction Fee / JAVA (0) | 2021.03.16 |