k 자리의 n 번째 회문을 찾기 위해 첫 번째 k 자리 수에서 n 번째 회문 번호를 찾을 때까지 반복할 수 있습니다. 이 접근 방식은 효율적이지 않습니다. 직접 시도해 볼 수 있습니다.
이제 k 자리의 n번째 회문을 찾는 효율적인 접근 방식을 살펴보겠습니다.
숫자에는 두 개의 반쪽이 있습니다. 전반전은 후반전과 동일합니다.
k자리의 n번째 숫자의 전반부는
k가 홀수이면 (n - 1) + 10 k/2 else(n-1)+10 k/2-1
k 자리 숫자가 있는 n 번째 숫자의 두 번째 절반은 숫자의 첫 번째 절반의 반대입니다. k가 홀수이면 숫자의 전반부에서 마지막 숫자를 자릅니다.
알고리즘
- 숫자 n과 k를 초기화합니다.
- k값을 사용하여 k자리 회문의 전반부의 길이를 구합니다.
- 회문의 전반부는 pow(10, length) + n - 1입니다.
- k가 홀수이면 회문의 전반부에서 마지막 숫자를 제거합니다.
- 전반부를 뒤집고 후반부를 인쇄합니다.
구현
다음은 위의 알고리즘을 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