[BOJ] 다음 팰린드롬 수

다음 팰린드롬 수 #

TimeLimit	MemoryLimit	Condition	TAG
2s	128MB	(1 <= N <= 50)	Implementation(구현)

팰린드롬 수는 앞으로 읽어도, 뒤로 읽어도 같은 숫자이다. 101, 4, 6666와 같은 숫자는 팰린드롬 수이고, 10, 564, 15452와 같은 숫자는 아니다. 어떤 수 N이 주어질 때, N보다 큰 팰린드롬 수 중에서 가장 작은 수를 출력한다.

참 요런 문제들이 진짜 설명이 간단하다. 우리의 목적은 주어진 수보다 큰 팰린드롬 수 중 작은 수를 출력하면 된다.

나는 이번 문제 풀면서 cpp string 함수들에 대해서 많이 알게되었다. 구현의 왕이 되기 위해서 더욱 단련하자…

(지금 학교에서 하고있는 100일 챌린지 때문에 1일 1포스팅(백준 또는 드림핵)을 하느라 설명이 거의 없는 점 죄송합니둥…)

정답 코드

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string solution(string num) {
    int n = num.length();
    string left = num.substr(0, (n + 1) / 2);
    string right = string(left.rbegin() + (n % 2), left.rend());

    if (left + right <= num) {
        int mid = (n - 1) / 2;
        bool allNines = true;
        for (int i = 0; i <= mid; i++) {
            if (num[i] != '9') {
                allNines = false;
                break;
            }
        }

        if (allNines) {
            return "1" + string(n - 1, '0') + "1";
        }

        for (int i = mid; i >= 0; i--) {
            if (num[i] < '9') {
                num[i]++;
                break;
            }
            num[i] = '0';
        }

        left = num.substr(0, (n + 1) / 2);
    }

    right = string(left.rbegin() + (n % 2), left.rend());
    return left + right;
}

int main() {
    string N;
    cin >> N;
    cout << solution(N) << "\n";
    return 0;
}

다음 팰린드롬 수#

다음 팰린드롬 수 #