백준 1334번: 다음 팰린드롬 수

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

 

주어진 50자리 이하의 수 보다 큰 가장 작은 팰린드롬 수를 구하는 문제이다. 자릿수가 크므로 정수형 타입을 쓸 수 없고 문자열을 비교해서 구해야 한다. 단순히 문자열로만 다루면 복잡하므로 문자 배열로 다루었으며, 가장 중요한 아이디어는 왼쪽(높은 자릿수)을 오른쪽(낮은 자릿수)으로 복사한다는 것이다.

 

가장 먼저 문자열 길이 기준 왼쪽의 문자열들을 오른쪽에 데칼코마니 하듯 복사해 주는 것이다. 그랬을 때, 주어진 수 보다 크면 그 수가 정답이다.

char[] baseNumber = s.toCharArray();
int length = baseNumber.length;

char[] targetNumber = baseNumber.clone();
for (int i = 0; i < length / 2; i++) {
    targetNumber[length - 1 - i] = targetNumber[i];
}

if (compare(targetNumber, baseNumber) > 0) {
    return new String(targetNumber);
}

private static int compare(char[] a, char[] b) {
    for (int i = 0; i < a.length; i++) {
        if (a[i] != b[i]) {
            return a[i] - b[i];
        }
    }
    return 0;
}

 

 

복사한 수가 주어진 수 보다 작다면 가운데에서 가장 가까운 왼쪽 수를 1 증가시킨 후 왼쪽의 숫자를 오른쪽으로 복사한다. 더하다가 10이 되면 받아 올림 처리를 해준다. 또한, 9999 -> 0099 처럼 자릿수가 증가할 수 있으며 이 또한 반영하여 맨 앞에 1을 추가해 준다.

int i = (length - 1) / 2;
while (i >= 0) {
    if (targetNumber[i] < '9') {
        targetNumber[i]++;
        targetNumber[length - 1 - i] = targetNumber[i];
        break;
    } else {
        targetNumber[i] = '0';
        targetNumber[length - 1 - i] = '0';
        i--;
    }
}

if (i < 0) {
    StringBuilder sb = new StringBuilder();
    sb.append('1');
    for (int j = 0; j < length - 1; j++) {
        sb.append('0');
    }
    sb.append('1');
    return sb.toString();
}

return new String(targetNumber);

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 다음팰린드롬수1334 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String number = br.readLine();
        br.close();
        System.out.print(solve(number));
        
    }
    
    private static String solve(String s) {
        char[] baseNumber = s.toCharArray();
        int length = baseNumber.length;
        
        char[] targetNumber = baseNumber.clone();
        for (int i = 0; i < length / 2; i++) {
            targetNumber[length - 1 - i] = targetNumber[i];
        }
        
        if (compare(targetNumber, baseNumber) > 0) {
            return new String(targetNumber);
        }
        
        int i = (length - 1) / 2;
        while (i >= 0) {
            if (targetNumber[i] < '9') {
                targetNumber[i]++;
                targetNumber[length - 1 - i] = targetNumber[i];
                break;
            } else {
                targetNumber[i] = '0';
                targetNumber[length - 1 - i] = '0';
                i--;
            }
        }
        
        if (i < 0) {
            StringBuilder sb = new StringBuilder();
            sb.append('1');
            for (int j = 0; j < length - 1; j++) {
                sb.append('0');
            }
            sb.append('1');
            return sb.toString();
        }
        
        return new String(targetNumber);
    }
    
    private static int compare(char[] a, char[] b) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] != b[i]) {
                return a[i] - b[i];
            }
        }
        return 0;
    }
}