양의 정수 N이 주어졌을 때, 각 자릿수를 임의의 순서로 재배열(원래 순서 포함)하여 새로운 수를 만들려고 합니다. 단, 맨 앞자리 숫자는 0이 아니어야 한다는 조건이 있습니다. 이렇게 만든 수가 2의 거듭제곱이 될 수 있는지 판별하는 것이 이 문제의 목표입니다. 예를 들어 N이 46이라면 자릿수를 뒤집어 64(= 2⁶)를 만들 수 있으므로 답은 true입니다.
접근 방법
핵심 아이디어는 자릿수 구성(signature) 비교입니다. 두 수가 같은 숫자들을 같은 개수만큼 포함하고 있다면, 서로 자릿수를 재배열한 관계임을 알 수 있습니다. 각 자릿수의 등장 정보를 하나의 정수 값으로 인코딩하여 비교하면 빠르고 간단하게 판별할 수 있습니다.
문제는 다음 단계로 해결할 수 있습니다:
정수 x를 입력받는 count 메서드를 정의합니다.
ret := 0 으로 초기화합니다.
x가 0이 아닌 동안 반복합니다:
ret := ret + 10^(x의 마지막 자릿수)
x := x / 10
ret을 반환합니다.
메인 로직에서는 다음을 수행합니다:
x := count(N)
i를 0부터 31까지 반복하며 count(2^i) == x인지 확인하고, 같으면 true를 반환합니다.
끝까지 일치하는 값이 없으면 false를 반환합니다.
동작 원리
count 함수는 각 자릿수 d에 대해 10^d를 더하는 방식으로 작동합니다. 예를 들어 46은 10⁴ + 10⁶ = 1,010,000이 되고, 64 역시 10⁶ + 10⁴ = 1,010,000으로 동일한 값을 가집니다. 즉, 자릿수 구성이 같은 수들은 항상 같은 시그니처를 갖습니다. 또한 int 범위 안의 2의 거듭제곱은 2⁰부터 2³¹까지 총 32개뿐이므로, 이들을 모두 검사하면 충분합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int count(int x){
int ret = 0;
while(x){
ret += pow(10, x % 10);
x /= 10;
}
return ret;
}
bool reorderedPowerOf2(int N) {
int x = count(N);
for(int i = 0; i < 32; i++){
if(count(1 << i) == x) return true;
}
return false;
}
};
main(){
Solution ob;
cout << (ob.reorderedPowerOf2(812));
}입력
812
출력
1
입력값 812의 자릿수 {8, 1, 2}를 재배열하면 128(= 2⁷)을 만들 수 있으므로 결과는 1, 즉 true입니다.