Python에서 N의 자릿수 순열이 M의 거듭제곱과 같은지 확인하는 방법

두 개의 양의 정수 n과 m이 주어졌다고 가정해 봅시다. 이때 2 ≤ n ≤ 10¹⁸이고 2 ≤ m ≤ n이라는 조건이 붙습니다. 우리가 확인해야 할 목표는 n의 자릿수를 모두 재배열해 만들 수 있는 순열(permutation) 중에서 m의 거듭제곱과 정확히 일치하는 값이 존재하는지 판별하는 것입니다. 만약 그런 순열이 하나라도 존재한다면 참, 존재하지 않는다면 거짓으로 답하면 됩니다.

예를 들어 n = 7182, m = 12가 입력으로 주어진 경우를 생각해 보겠습니다. 7182의 자릿수를 재배열하면 1728을 만들 수 있고, 1728은 12³과 같습니다. 따라서 이 경우에는 'n의 자릿수 순열 중 m의 거듭제곱과 같은 값이 존재한다'고 답할 수 있습니다.

즉, 입력이 n = 7182, m = 12라면 출력은 다음과 같습니다.

'n의 자릿수 순열 중 m의 거듭제곱과 같은 값이 존재합니다'

해결 접근 방법

이 문제는 크게 두 단계로 나누어 해결할 수 있습니다. 먼저 m의 거듭제곱 값들을 범위 내에서 모두 생성한 뒤, n과 각 거듭제곱 값의 자릿수 구성을 비교하는 방식입니다. 전체 흐름을 단계별로 정리하면 다음과 같습니다.

1단계: 자릿수 비교 함수(check_power) 작성

check_power(n, m) 함수를 정의합니다.
빈 리스트 temp_arr_1과 temp_arr_2를 준비합니다.
n이 0보다 큰 동안 n을 10으로 나눈 나머지를 temp_arr_1 끝에 추가하고, n을 10으로 나눈 몫(정수 나눗셈)으로 갱신합니다.
m에 대해서도 동일한 과정을 반복해 temp_arr_2를 채웁니다.
두 리스트를 각각 집합(set)으로 변환했을 때 서로 같으면 True를 반환하고, 그렇지 않으면 False를 반환합니다.

2단계: m의 거듭제곱 목록 생성 및 검사

크기 100짜리 power_array 리스트를 0으로 초기화합니다.
검사 상한값 max_range를 10¹⁸로 설정합니다.
power_array[0]에 m을 저장하고 i를 1로 설정합니다.
power_array[i - 1] * m이 max_range보다 작은 동안 power_array[i]에 이전 값에 m을 곱한 결과를 저장하고 i를 1씩 증가시킵니다.
생성된 모든 거듭제곱 값 j에 대해 check_power(n, power_array[j])가 True라면 성공 메시지를 반환합니다.
모든 후보를 검사한 후에도 일치하는 값이 없다면 실패 메시지를 반환합니다.

이제 실제 구현 코드를 통해 더 자세히 이해해 보겠습니다.

Python 구현 예제

def check_power(n, m):
    temp_arr_1 = []
    temp_arr_2 = []
    while (n > 0):
        temp_arr_1.append(n % 10)
        n //= 10
    while (m > 0):
        temp_arr_2.append(m % 10)
        m //= 10
    if (set(temp_arr_1) == set(temp_arr_2)):
        return True
    return False

def solve(n, m):
    power_array = [0] * 100
    max_range = pow(10, 18)
    power_array[0] = m
    i = 1
    while (power_array[i - 1] * m < max_range):
        power_array[i] = power_array[i - 1] * m
        i += 1
    for j in range(i):
        if (check_power(n, power_array[j])):
            return 'n의 자릿수 순열 중 m의 거듭제곱과 같은 값이 존재합니다'
    return 'n의 어떤 자릿수 순열도 m의 거듭제곱과 같지 않습니다'

n, m = 7182, 12
print(solve(n, m))

실행 결과

입력:

7182, 12

출력:

n의 자릿수 순열 중 m의 거듭제곱과 같은 값이 존재합니다

동작 원리와 시간 복잡도

check_power 함수는 숫자를 한 자리씩 분해해 리스트에 담은 뒤 집합으로 비교하므로, 처리 시간은 숫자의 자릿수에 비례합니다. solve 함수는 m의 거듭제곱을 10¹⁸ 미만까지만 생성하므로 검사해야 할 후보는 최대 약 60개(log₂(10¹⁸) ≈ 60) 수준입니다. 따라서 전체 시간 복잡도는 대략 O(log_m(10¹⁸) × 자릿수)로 매우 효율적이며, n이 최대 10¹⁸까지 커져도 충분히 빠르게 동작합니다.

참고: 더 엄격한 순열 비교가 필요하다면

위 코드는 집합(set)을 사용하기 때문에 자릿수의 '종류'만 비교하며, 각 자릿수의 개수까지 일치하는지는 확인하지 않습니다. 예를 들어 1122와 12는 집합 기준으로는 같은 자릿수 집합 {1, 2}를 가져 같다고 판정될 수 있습니다. 자릿수별 개수까지 완벽하게 비교하려면 set 비교 대신 sorted(temp_arr_1) == sorted(temp_arr_2)처럼 정렬된 리스트를 비교하거나, collections.Counter를 활용해 자릿수 빈도를 비교하는 방식으로 코드를 수정하면 됩니다.