C++로 K자리 수의 N번째 회문 구하기

K자리 회문 중 N번째 회문을 찾는 문제는 코딩 테스트나 알고리즘 학습에서 자주 등장하는 주제입니다. 이 글에서는 비효율적인 방법과 효율적인 방법을 비교하고, C++로 구현하는 과정까지 자세히 살펴보겠습니다.

비효율적인 접근 방식

가장 단순하게 떠올릴 수 있는 방법은 가장 작은 K자리 수부터 시작하여 한 숫자씩 증가시키면서 회문인지 검사하고, N번째 회문을 발견할 때까지 반복하는 것입니다. 하지만 이 방법은 회문이 아닌 수까지 모두 확인해야 하므로 탐색 범위가 매우 넓어져 비효율적입니다. 직접 구현해 보면 그 차이를 체감할 수 있습니다.

효율적인 접근 방식

회문은 앞에서 읽으나 뒤에서 읽으나 같은 수입니다. 즉, 모든 회문은 두 개의 절반으로 나눌 수 있으며, 후반부는 전반부를 뒤집은 형태와 같습니다. 이 대칭성을 활용하면 전반부만 계산하면 되므로 전체 수를 일일이 확인할 필요가 없습니다.

K자리 수 중 N번째 회문의 전반부는 다음과 같이 구할 수 있습니다.

k가 홀수인 경우: (n - 1) + 10^k/2
k가 짝수인 경우: (n - 1) + 10^{k/2 - 1}

후반부는 전반부 숫자를 뒤집은 값이 됩니다. 단, k가 홀수인 경우에는 전반부의 마지막 자릿수를 먼저 제거한 뒤 뒤집어야 합니다. 이는 가운데 자릿수가 중복되지 않도록 하기 위함입니다.

알고리즘

n과 k를 초기화합니다.
k 값을 이용하여 k자리 회문의 전반부 길이를 구합니다.
회문의 전반부는 pow(10, length) + n - 1로 계산합니다.
k가 홀수라면 전반부에서 마지막 자릿수를 제거합니다.
전반부를 뒤집어 후반부로 출력합니다.

C++ 구현

위 알고리즘을 C++로 구현한 코드는 다음과 같습니다.

#include<bits/stdc++.h>
using namespace std;
void findNthPalindrome(int n, int k) {
   int temp = (k & 1) ? (k / 2) : (k / 2 - 1);
   int palindrome = (int)pow(10, temp);
   palindrome += n - 1;
   cout << palindrome;
   if (k & 1) {
      palindrome /= 10;
   }
   while (palindrome) {
      cout << palindrome % 10;
      palindrome /= 10;
   }
   cout << endl;
}
int main(){
   int n = 7, k = 8;
   findNthPalindrome(n ,k);
   return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

10066001

동작 원리 살펴보기

예제에서 n = 7, k = 8인 경우를 단계별로 분석해 보겠습니다.

k = 8은 짝수이므로 temp = 8 / 2 - 1 = 3이 됩니다.
palindrome = 10³ = 1000이고, 여기에 n - 1 = 6을 더해 1006이 됩니다. 이것이 전반부입니다.
k가 짝수이므로 마지막 자릿수 제거 과정은 생략합니다.
전반부 1006을 뒤집으면 6001이 되고, 이를 이어 붙여 최종 결과인 10066001을 얻습니다.

10066001은 실제로 앞뒤가 대칭인 8자리 회문이며, 8자리 회문 중 7번째에 해당합니다.

시간 복잡도

이 방법은 전반부를 한 번 계산하고 이를 뒤집기만 하면 되므로, 무작정 반복 탐색하는 방식과 달리 k에 비례하는 선형 시간 O(k) 안에 답을 구할 수 있습니다. N이 아무리 커도 계산량이 거의 변하지 않는다는 점이 큰 장점입니다.