[BaekJoon] 1334 다음 팰린드롬 수

1.  문제 링크

2.  문제

요약

• N이 주어질 때, N보다 큰 앞으로 읽어도, 뒤로 읽어도 같은 수인 팰린드롬 수 중 가장 작은 수를 찾는 문제입니다.
• 입력: 첫 번째 줄에 최대 50자리인 양의 정수인 N이 주어집니다.
• 출력: N보다 큰 팰린드롬 수 중 가장 작은 수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigInteger;

public class Main {
	public String reverseString(String num) {
		String result = "";
		for(int i = num.length(); i > 0; i--) {
			result += num.substring(i - 1, i);
		}
		return result;
	}
	
	public String getMinPallindrom(String num) {
		if(num.length() == 1 || num.equals("10")) {
			int n = Integer.parseInt(num);
			if(n < 9) {
				n++;
				return Integer.toString(n);
			} else {
				return "11";
			}
		}
		String r_num = "";
		if(num.length() % 2 == 1) {
			r_num += num.substring(0, num.length() / 2) + num.substring(num.length() / 2, num.length() / 2 + 1) + num.substring(num.length() / 2 + 1, num.length());
		} else {
			r_num += num.substring(0, num.length() / 2) + num.substring(num.length() / 2, num.length());
		}
		if(r_num.compareTo(num) > 0) {
			return r_num;
		} else {
			String result;
			BigInteger int_num = new BigInteger(num);
			int_num = int_num.add(BigInteger.ONE);
			num = int_num.toString();
			int half = num.length() / 2;
			if(num.length() % 2 == 1) {
				String left = num.substring(0, half);
				String mid = num.substring(half, half + 1);
				String right = num.substring(half + 1, num.length());
				if(reverseString(left).compareTo(right) >= 0) {
					result = left + mid + reverseString(left);
				} else {
					if(mid.equals("9")) {
						mid = "0";
						int prev_length = left.length();
						BigInteger bnum = new BigInteger(left);
						bnum = bnum.add(BigInteger.ONE);
						left = bnum.toString();
						if(left.length() > prev_length) {
							result = left + reverseString(left);
						} else {
							result = left + mid + reverseString(left);
						}
					} else {
						result = left + Integer.toString(Integer.parseInt(mid) + 1) + reverseString(left);
					}
				}
			} else {
				String left = num.substring(0, half);
				String right = num.substring(half, num.length());
				if(reverseString(left).compareTo(right) >= 0) {
					result = left + reverseString(left);
				} else {
					int prev_length = left.length();
					BigInteger bnum = new BigInteger(left);
					bnum = bnum.add(BigInteger.ONE);
					left = bnum.toString();
					if(prev_length < left.length()) {
						result = left.substring(0, left.length() - 1) + reverseString(left);
					} else {
						result = left + reverseString(left);
					}
				}
			}
			return result;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String num = br.readLine();
		br.close();
		Main m = new Main();
		bw.write(m.getMinPallindrom(num) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 팰린드롬 수는 앞에서 읽어도 뒤에서 읽어도 같은 수이므로 중간을 기준으로 왼쪽과 오른쪽이 같아야 하기 때문에 중간을 기준으로 왼쪽과 오른쪽으로 수를 나누고 왼쪽 또는 오른쪽을 뒤집은 수를 오른쪽 또는 왼쪽으로 나눈 수와 이어붙여 팰린드롬 수를 만들 수 있습니다.
• 위 방법을 이용하여 답을 구해나갈 것입니다.

• 만약 N이 한 자릿수이고 9가 아니라면 N+1을 했을 때에도 한 자릿수이기 때문에 N+1이 답이 됩니다.
• 또한 만약 N이 9 또는 10이라면 이보다 큰 수 중 가장 작은 팰린드롬 수는 11이 되기 떄문에 11이 답이 됩니다.
• 만약 위 두 경우 모두가 아니라면 해당 수의 자릿수가 짝수인지 홀수인지 확인합니다.

• 만약 홀수라면
1. N을 앞에서부터 N/2개, N/2번째 수, 나머지 N/2개로 수를 나눕니다. 편의상 앞에서부터 left, mid, right로 부르겠습니다.
2. 이렇게 나눈 수에서 left를 뒤집은 수를 구하고 이 수와 right를 비교하여 만약 left를 뒤집은 수가 더 크다면 (left, mid, left를 뒤집은 수)를 이은 수가 팰린드롬 수가 되며 답이 됩니다.
3. 만약 right가 더 크거나 같다면 N에 1을 더해주고 해당 수의 자릿수가 짝수인지 홀수인지 확인합니다.


4. 만약 홀수라면
• 4-1. 1번과 같이 left, mid, right로 나누고 2번과 같은 작업을 진행합니다.
• 4-2. 만약 left를 뒤집은 수가 right보다 크거나 같다면 (left, mid, left를 뒤집은 수)를 이은 수가 답이 됩니다.
• 4-3. N보다 큰 팰린드롬 수를 만들 때 자릿수가 홀수인 경우에는 left를 뒤집은 수가 right보다 작다면 mid의 값을 1 올린 후에 left를 뒤집은 값을 left, mid를 이은 값에 이어주면 N보다 크면서 가장 작은 팰린드롬 수가 됩니다.


• 4-3-1.  그렇기 때문에 만약 right가 더 크다면 mid가 9인지 확인하고 만약 9라면 mid를 0으로 만들어주고 left에 1을 더해줍니다.
• 4-3-2 left에 1을 더해줬을 때 자릿수가 변경되었다면 left와 left를 뒤집은 수를 이어준 값이 답이 됩니다.
• left에 1을 더해줬을 때 자릿수가 변경되었다는 것은 1000과 같이 10의 거듭제곱 수이기 때문에 이 수를 뒤집은 수와 left, mid를 이어준 수를 그대로 이어준다면 자릿수가 2자리 늘어나는 셈이 되기 때문에 mid를 제외하고 이어줍니다.
• 4-3-3 자릿수가 변경되지 않았다면 (left, 1을 더해준 mid, left를 뒤집은 수)를 이어준 값이 답이 됩니다.


• 4-3-1.  만약 mid가 9가 아니라면 1-3-3과 같이 (left, 1을 더해준 mid, left를 뒤집은 수)를 이어준 값이 답이 됩니다.


5. 만약 짝수라면
• 5-1. N이라는 수를 앞에서부터 N/2개, 나머지 N/2개로 수를 나눕니다. 편의상 left, right라고 부르겠습니다.
• 5-2. 만약 left를 뒤집은 수가 right보다 크거나 같다면 left와 left를 뒤집은 수를 이은 수가 답이 됩니다.
• 5-3. N보다 큰 팰린드롬 수를 만들 때 자릿수가 짝수인 경우에는 left를 뒤집은 수가 right보다 작다면 left의 값을 1 올린 후에 left를 뒤집은 값을 left와 이어주면 N보다 크면서 가장 작은 팰린드롬 수가 됩니다.


• 5-3-1.  그렇기 때문에 만약 right가 더 크다면 left에 1을 더해줍니다.
• 5-3-2 left에 1을 더해줬을 때 자릿수가 변경되었다면 left에서 가장 뒷자리 수를 제외한 수와 left를 뒤집은 수를 이어준 수가 답이 됩니다.
• 자릿수가 변경되었다는 것은 1000과 같이 10의 거듭제곱 수이기 때문에 이를 뒤집은 수와 그대로 이어주면 자릿수가 2자리가 늘어나기 때문에 left의 가장 뒷자리 수를 제외합니다.
• 5-3-3 자릿수가 변경되지 않았다면 left와 left를 뒤집은 수를 이어주면 그 수가 답이 됩니다.