C++에서 가장 가까운 회문(팰린드롬) 찾기

문제 개요

숫자 n이 주어졌을 때, n과의 절대 차이가 가장 작은 회문(팰린드롬)을 찾는 것이 목표입니다. 회문이란 앞에서 읽으나 뒤에서 읽으나 같은 수를 의미하며, 정답은 n보다 작을 수도 있고 클 수도 있습니다. 예를 들어 n이 145라면 가장 가까운 회문은 141입니다.

접근 방식: 절반 미러링

모든 숫자를 하나씩 확인하는 대신, n의 왼쪽 절반을 기준으로 오른쪽 절반을 거울처럼 뒤집어 붙이면 회문을 만들 수 있다는 점에 착안합니다. 왼쪽 절반을 그대로 사용하는 경우, 1을 뺀 경우, 1을 더한 경우 세 가지만 시도하면 충분하고, 자릿수 변화가 생기는 경계값(예: 99, 101, 999, 1001 등)도 함께 후보에 포함하면 모든 경우를 빠짐없이 커버할 수 있습니다.

알고리즘 단계

sn := 문자열 n의 길이
sn이 1이라면, n[0]에서 1을 뺀 문자 하나짜리 문자열을 반환합니다. (한 자리 수는 모두 회문이므로, 자기 자신을 제외한 가장 가까운 수는 바로 옆 숫자입니다.)
half_sn := (sn + 1) / 2 — 왼쪽 절반의 길이
half_val := n의 앞 half_sn자리를 정수로 변환한 값
후보 배열 candidates 초기화: {10^sn − 1, 10^(sn−1) − 1, 10^(sn−1) + 1, 10^sn + 1}
배열 fmdc := {half_val, half_val − 1, half_val + 1}
fmdc의 각 값 c에 대해 다음을 수행합니다:
- rev := c를 문자열로 변환
- sn이 홀수라면 rev의 마지막 문자를 제거 (중앙 자릿수 중복 방지)
- rev를 뒤집은 뒤, c와 rev를 이어 붙인 새로운 회문을 candidates에 추가
candidates를 오름차순으로 정렬합니다.
val := n을 정수로 변환한 값
각 candidate에 대해:
- candidate == val이면 건너뜁니다 (자기 자신 제외).
- diff := |candidate − val|
- diff < min_diff이면 min_diff := diff, ans := candidate의 문자열 표현으로 갱신합니다.
ans를 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    string nearestPalindromic(string n) {
        int sn = n.size();
        if(sn == 1){
        return string(1, --n[0]);
    }
    int half_sn = (sn+1)/2;
    long half_val = stol(n.substr(0, half_sn));
    vector<long> candidates = {pow(10, sn)-1, pow(10, sn-1)-1, pow(10, sn-1)+1, pow(10, sn)+1};
    vector <long> fmdc = {half_val, half_val-1,half_val+1};
    for(long c:fmdc){
        string rev = to_string(c);
        if(sn%2)rev.pop_back();
        reverse(rev.begin(),rev.end());
        candidates.push_back(stol(to_string(c) + rev));
    }
    sort(candidates.begin(), candidates.end());
    string ans;
    long val = stol(n), min_diff = INT_MAX;
    for(long candidate : candidates){
        if(candidate == val)continue;
        long diff = labs(candidate - val);
        if(diff < min_diff){
            min_diff = diff;
            ans = to_string(candidate);
            }
        }
        return ans;
    }
};
main(){
    Solution ob;
    cout << (ob.nearestPalindromic("145"));
}

입력

“145”

출력

동작 과정 살펴보기

n = 145일 때 sn = 3, half_sn = 2, half_val = 14입니다. fmdc = {14, 13, 15}로부터 생성되는 회문 후보는 각각 141, 131, 151이며, 여기에 경계값 999, 99, 101, 10001이 추가됩니다. 145와의 차이를 비교하면 141이 4로 가장 작으므로 최종 답은 141이 됩니다.

복잡도 분석

후보의 개수는 입력 크기와 무관하게 항상 일정하며, 각 후보의 생성과 비교에는 문자열 길이에 비례하는 O(sn) 시간이 걸립니다. 따라서 전체 시간 복잡도는 O(sn)으로, 숫자를 하나씩 증감하며 탐색하는 무식한 방식보다 훨씬 효율적입니다.

C++에서 가장 가까운 회문(팰린드롬) 찾기 – 절반 미러링 알고리즘