C++에서 가장 가까운 회문 찾기

<시간/>

숫자 n이 있다고 가정하면 회문인 가장 가까운 숫자를 가져와야 합니다. 따라서 회문은 절대 차이가 작은 수보다 작거나 클 수 있습니다. 따라서 숫자가 145와 같으면 결과는 141이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

sn :=n의 크기
sn이 1과 같으면 -
- n[0]을 1만큼 감소시키고 크기가 n[0]인 1의 문자열을 반환합니다.
half_sn :=(sn + 1) / 2
half_val :=stol(인덱스 0에서 half_sn까지 n의 부분 문자열
배열 후보 정의 ={10^(sn) – 1, 10^(sn - 1) - 1, 10^(sn - 1) + 1, 10^(sn)+1
배열 정의 fmdc ={ half_val, half_val - 1, half_val + 1 }
fmds
- rev :=c를 문자열로 변환
- sn mod 2가 0이 아니면 -
  - rev에서 마지막 요소 삭제
- 배열 rev 반전
- 후보의 끝에 c 삽입
배열 후보 정렬
val :=n을 정수로
후보자의 각 후보자에 대해 −
- 후보가 val과 같으면 -
  - 다음 부분은 무시하고 다음 반복으로 건너뜁니다.
- diff :=abs|후보 – val|
- diff
- min_diff :=차이
- ans :=후보를 문자열로 변환

반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

#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”

C++에서 가장 가까운 회문 찾기

예

입력

출력