[BOJ] 1334 - 다음 팰린드롬 수

https://www.acmicpc.net/problem/1334

BOJ - 다음 팰린드롬 수

문제 유형: 문자열 처리, 구현, 조건분기

문제 난이도: Gold V

시간 제한: 1초

메모리 제한: 128MB

 

문제

팰린드롬 수는 앞으로 읽어도, 뒤로 읽어도 같은 숫자이다. 101, 4, 6666와 같은 숫자는 팰린드롬 수이고, 10, 564, 15452와 같은 숫자는 아니다.

어떤 수 N이 주어질 때, N보다 큰 팰린드롬 수 중에서 가장 작은 수를 출력한다.

 

입력

첫째 줄에 N이 주어진다. N은 최대 50자리인 양의 정수이다. 첫 숫자는 0이 아니다.

 

출력

첫째 줄에 문제의 정답을 출력한다.

 

풀이

만약 n의길이가 1이라면, +1한것을 출력하면 끝이다.

(예외: 9는 11을 출력)

 

n의 길이가 홀수인 경우:

우선, 왼쪽 절반 prefix(0 ~ len/2)만 뗀 것을 left라 하자.

left를 뒤집은 것을 right로 초기화 한다.

left + n[len/2] + right가 n보다 크다면(길이가 같기에 사전순비교를 해도 된다), 이를 출력하면 된다.

 

아니라면, 가운데 수를 1 늘리는 것을 시도한다.

  만약 캐리가 발생한다면, left에도 반영해서 올림을 만들어주면 된다.

    만약 캐리때문에 맨 앞까지 0이 된다면, 맨 앞에 1을 붙인다.

     그러고 left + left반전을 붙이면 된다. (ex. 999 -> 1001)

    맨 앞까지 0이된 건 아니라면, right를 변형된 left로부터 복사하여 뒤집어 저장시킨다.

     그러고 left + '0' + right를 출력하면 된다. (ex. 899 -> 909)

 

n의 길이가 짝수인 경우:

왼쪽절반인 left와 그의 반전인 right를 만들고, left + right가 n보다 크다면 출력하면 된다.

아니라면? 홀수에서 가운데에 1을 올린것처럼 left의 맨 끝부터 작업해주면 된다.

 만약 캐리가 left의 맨 앞까지 반영되었다면, "1" + left + left문자열을 만들고, 맨 뒤를 1로 해서 출력하면 된다. (9999 -> 10001)

 그 정도의 캐리는 아니라면, right에 캐리가 반영된 left를 뒤집어서 저장하고, left + right를 출력하면 된다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[]) {
    string n;
    cin >> n;

    int len = n.size();
    if (len == 1) {
        if (n == "9") {
            cout << "11\n";
        } else {
            n[0]++;
            cout << n << "\n";
        }
        return 0;
    }
    if (len % 2 == 1) {
        string left = n.substr(0, len / 2);
        string right = left;
        reverse(right.begin(), right.end());

        string temp = left + n[len / 2] + right;
        if (temp > n) {
            cout << temp << "\n";
        } else if (temp[len / 2] <= '8') {
            temp[len / 2]++;
            cout << temp << "\n";
        } else {
            int k = len / 2 - 1;
            while (k >= 0) {
                if (left[k] == '9') {
                    left[k] = '0';
                } else {
                    left[k]++;
                    break;
                }
                k--;
            }
            if (left[0] == '0') {
                left = "1" + left;
                right = left;
                reverse(right.begin(), right.end());
                cout << left + right << "\n";
            } else {
                right = left;
                reverse(right.begin(), right.end());
                cout << left + '0' + right << "\n";
            }
        }
    } else {
        string left = n.substr(0, len / 2);
        string right = left;
        reverse(right.begin(), right.end());
        if (left + right > n) {
            cout << left + right << "\n";
        } else {
            int k = len / 2 - 1;
            while (k >= 0) {
                if (left[k] == '9') {
                    left[k] = '0';
                } else {
                    left[k]++;
                    break;
                }
                k--;
            }
            if (left[0] == '0') {
                string ans = "1" + left + left;
                ans.back() = '1';
                cout << ans << "\n";
            } else {
                right = left;
                reverse(right.begin(), right.end());
                cout << left + right << "\n";
            }
        }
    }

    return 0;
}