[LeetCode] 564. Find the Closest Palindrome

https://leetcode.com/problems/find-the-closest-palindrome/description/?envType=daily-question&envId=2024-08-24

leetcode - Find the Closest Palindrome

문제 유형 : 팰린드롬, 회문, 문자열 처리

문제 난이도 : Hard

 

문제

Given a string n representing an integer, return the closest integer (not including itself), which is a palindrome. If there is a tie, return the smaller one.

The closest is defined as the absolute difference minimized between two integers.

 

정수를 표현하는 문자열 n이 주어진다. 자신을 제외한 가장 가까운 팰린드롬을 구하시오.

같은 가까운 팰린드롬들이 존재하면, 더 작은 걸 반환하시오.

 

풀이

기본적으로, 10 이하의 수들은 (자신-1)을 반환하면 된다. 한 자리 숫자는 항상 팰린드롬이기 때문이다. 10은 9와 11모두 거리가 1인 팰린드롬들을 가지는데, 9가 더 작으므로 함께 적용된다.

거기다가, 11의 경우, 9가 가장 인접한 팰린드롬이다. 9 다음으로는 22가 있다.

 

999의 가장 가까운 팰린드롬은 1001,

1001, 1000의 가장 가까운 팰린드롬은 999.

이와 같이, "1" +((기존 문자열의 길이-1)개 * "0") + "1" 또는 (기존 문자열의 길이 -1)개 * "9")형식의 문자열들 역시 기본적으로 정답 후보이다.

 

이제, 주어진 숫자 문자열을 기반으로 팰린드롬을 만들면 되는데, 하나 규칙을 발견할 수 있다.

123 -> 121,

1234 -> 1221.

공통점은 낮은 자리 수가 높은 자리 수에 맞춰야 한다는 것이다. 그래야 기존 숫자로부터의 거리가 좁기 때문이다.

그렇기에, 우리는 주어진 문자열 n에 대해 앞쪽 left prefix들만 가져와서, 그 역 문자열들을 뒤에 붙이기만 하면, 최적의 정답 후보가 될 수 있는 것이다.

단, 중간의 수를 조금 조작할 필요가 있다.

예를 들어, 1283의 가장 가짜운 팰린드롬은 1331인데, 위처럼 원본에 대해서만 바꿔버리면 1221이 나와서 좀 더 먼 경우를 고르게 된다.

그래서, left prefix들의 일의 자리 수, 즉 가운데가 될 수들을 -1, 원본, +1모두 저장해놓는다.

그리고 그 각각의 역문자열을 만들어서 이어붙여서 후보에 등록하면 된다.

예를 들어, 1283이면 left prefix는 "12"가 되는데, "11", "12", "13"을 만들어서 후보에 "1111", "1221", "1331"을 등록시켜놓는 것이다.

단, 홀수인 경우는 역문자열을 붙일 때 유의하라. "123"의 경우 "12"로 left prefix를 떼오는데, "1221"이 나오지 않고 "121"이 나오도록 하라는 뜻이다.

 

그러면, 후보들("1000~0001", "999~999", "중간 숫자 -1로 생성한 팰린드롬", "원본으로 만든 팰린드롬", "중간숫자 +1로 생성한 팰린드롬")이 있는데, 이 중에서 가장 원본 숫자 n과 수의 차가 적은 것을 반환하면 된다.

 

코드

C++

class Solution {
public:
    string nearestPalindromic(string n) {
        long long num = stoll(n);
        int len = n.size();
        if(num <= 10) return to_string(num-1);
        if(num == 11) return "9";

        vector<string> ans;
        long long prefix = stoll(n.substr(0, (len+1)/2));

        vector<long long> candidates = {prefix-1, prefix, prefix+1};

        for(long long cand : candidates) {
            string candStr = to_string(cand);
            if(len%2) {
                candStr = candStr + string(candStr.rbegin()+1, candStr.rend());
            } else {
                candStr = candStr + string(candStr.rbegin(), candStr.rend());
            }
            ans.push_back(candStr);
        }

        ans.push_back("1" + string(len-1, '0') + "1");
        ans.push_back(string(len-1, '9'));

        string res;
        long long minDiff = LLONG_MAX;

        for (auto &cand : ans) {
            long long x = stoll(cand);
            if(x == num) continue;
            long long diff = abs(x - num);
            if(diff < minDiff || (diff == minDiff && x < stoll(res))) {
                res = cand;
                minDiff = diff;
            }
        }
        return res;
    }
};