큰 양의 정수 N이 주어졌을 때, N의 자릿수를 재배열하여 만들 수 있는 순열 중에서 회문(palindrome)이면서 동시에 3으로 나누어떨어지는 수가 하나라도 존재하는지 확인하는 문제입니다.
예를 들어 입력이 132213이라고 가정해 보겠습니다. 자릿수를 재배열하면 123321을 만들 수 있는데, 이 수는 거꾸로 읽어도 같은 회문이면서 자릿수 합이 12이므로 3의 배수이기도 합니다. 따라서 출력은 "하나 이상의 순열이 회문이면서 3의 배수"가 됩니다.
핵심 아이디어
모든 순열을 일일이 생성하는 것은 비효율적입니다. 대신 다음 두 가지 수학적 성질을 활용하면 자릿수만 확인해서 빠르게 판단할 수 있습니다.
1. 3의 배수 판별
어떤 수가 3으로 나누어떨어지는지는 각 자릿수의 합으로 알 수 있습니다. 자릿수의 합이 3의 배수라면, 그 자릿수들을 어떻게 재배열하더라도 결과는 항상 3의 배수입니다. 반대로 자릿수의 합이 3의 배수가 아니면 어떤 순열도 3의 배수가 될 수 없습니다.
2. 회문 형성 조건
자릿수들을 재배열하여 회문을 만들려면, 등장 횟수가 홀수인 자릿수가 최대 1개여야 합니다. 짝수 길이의 수는 홀수 빈도 자릿수가 없어야 하고, 홀수 길이의 수는 정확히 하나의 자릿수가 가운데 위치할 수 있습니다.
알고리즘 단계
- 크기 10의 배열 digit_array를 0으로 초기화합니다 (각 자릿수의 등장 횟수 저장용).
- input_sum := 0 으로 초기화합니다.
- input_num이 0이 아닌 동안 반복합니다:
- input_sum에 마지막 자릿수(input_num mod 10)를 더합니다.
- digit_array[input_num mod 10] 값을 1 증가시킵니다.
- input_num을 10으로 나눈 몫으로 갱신합니다.
- input_sum mod 3이 0이 아니면 False를 반환합니다.
- index_odd := 0 으로 초기화합니다.
- i를 0부터 9까지 반복하며 digit_array[i]가 홀수이면 index_odd를 1 증가시킵니다.
- index_odd가 1보다 크면 "회문이면서 3의 배수인 순열이 없음"을 반환합니다.
- 그렇지 않으면 "하나 이상의 순열이 회문이면서 3의 배수임"을 반환합니다.
구현 예제
def solve(input_num):
digit_array = [0] * 10
input_sum = 0
while (input_num) :
input_sum += input_num % 10
digit_array[input_num % 10] += 1
input_num //= 10
if (input_sum % 3 != 0):
return False
index_odd = 0
for i in range(10) :
if (digit_array[i] % 2 != 0):
index_odd += 1
if (index_odd > 1):
return "No permutation is a palindrome and is divisible by three"
else:
return "One or more permutation is a palindrome and is divisible by three"
input_num = 132213
print(solve(input_num))입력
132213
출력
One or more permutation is a palindrome and is divisible by three
복잡도 분석
이 알고리즘은 입력 숫자의 자릿수만 한 번 순회하므로 시간 복잡도는 O(log N)이며, 추가 메모리는 크기 10의 고정 배열만 사용하므로 공간 복잡도는 O(1)입니다. 실제로 모든 순열을 생성하는 방식(최악의 경우 자릿수의 계승에 비례)과 비교하면 극적으로 효율적인 접근법입니다.