양의 정수 N이 주어졌을 때, N의 각 자릿수를 임의의 순서로 재배열(원래 순서 포함)할 수 있습니다. 단, 맨 앞자리 숫자는 0이 아니어야 한다는 조건이 붙습니다. 이때 재배열된 숫자가 2의 거듭제곱이 될 수 있는지 판별하는 것이 이 문제의 목표입니다.
예를 들어 입력값이 N = 812라고 가정해 봅시다. 812의 자릿수를 재배열하면 128, 218, 281, 821 등 다양한 숫자를 만들 수 있는데, 그중 128은 2⁷이므로 결과는 True가 됩니다.
문제 해결 접근 방식
이 문제는 정렬을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 두 숫자가 자릿수의 재배열 관계에 있으면, 문자열로 변환한 뒤 정렬했을 때 반드시 같은 결과가 나온다는 점입니다.
구체적인 알고리즘은 다음과 같습니다.
- 기준값 i를 1로 초기화합니다.
- i가 10억(1,000,000,000) 이하인 동안 반복합니다.
- i를 문자열로 변환한 후 s에 저장하고, 문자들을 오름차순으로 정렬합니다.
- 마찬가지로 n도 문자열로 변환해 t에 저장한 뒤 정렬합니다.
- s와 t가 동일하면 True를 반환합니다.
- 그렇지 않으면 i에 2를 곱하고 다음 반복으로 넘어갑니다.
모든 2의 거듭제곱(1, 2, 4, 8, ..., 2³⁰)을 검사한 후에도 일치하는 경우가 없으면 False를 반환합니다.
파이썬 구현 예제
아래 코드를 통해 실제 구현 과정을 살펴보겠습니다.
def solve(n):
i=1
while i<=1000000000:
s=str(i)
s=''.join(sorted(s))
t=str(n)
t=''.join(sorted(t))
if s==t:
return True
i=i*2
return False
N = 812
print(solve(N))입력
812
출력
True
동작 원리 설명
입력값 812를 문자열로 정렬하면 "128"이 되고, 2의 거듭제곱 중 하나인 128을 정렬해도 역시 "128"이 됩니다. 두 정렬 결과가 일치하기 때문에 함수는 True를 반환합니다.
이 방식은 최대 31개의 2의 거듭제곱만 검사하면 되고, 각 검사마다 자릿수 정렬에 O(d log d) 시간(d는 자릿수)이 소요되므로 전체적으로 매우 효율적입니다. 별도의 순열 생성 없이도 문제를 선형 로그 시간 안에 해결할 수 있다는 점이 이 접근법의 큰 장점입니다.