[BaekJoon] 1254 팰린드롬 만들기

1.  문제 링크

2.  문제

요약

• 문자열 S가 주어질 때 S라는 문자열 뒤에 0개 이상의 문자를 추가하여 팰린드롬을 만드는데 이 때 가장 짧은 팰린드롬의 길이를 구하는 문제입니다.
• 입력: 첫 번째 줄에 알파벳 소문자로만 이루어져있는 최대 길이가 50인 문자열 S가 주어집니다.
• 출력: 첫 번째 줄에 문자열 S 뒤에 0개 이상의 문자를 추가하여 만든 가장 짧은 팰린드롬의 길이를 출력합니다.

3.  소스코드

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

public class Main {
	public boolean isPalindrome(String str) {
		int start = 0;
		int end = str.length() - 1;
		while(start <= end) {
			if(str.charAt(start) != str.charAt(end)) {
				return false;
			}
			start++;
			end--;
		}
		return true;
	}
	
	public int getPalindromeNum(String input) {
		int len = input.length();
		for(int i = 0; i < len; i++) {
			if(isPalindrome(input.substring(i))) {
				return len + i;
			}
		}
		return 0;
	}
	
	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 input = br.readLine();
		br.close();
		Main m = new Main();
		bw.write(m.getPalindromeNum(input) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 현재 주어진 문자열부터 시작해서 앞에서부터 길이를 하나씩 줄여가며 해당 문자열이 팰린드롬이 되는지 확인하고 팰린드롬이 되는 순간에 줄여간 문자열들을 역순으로 뒤에 붙여준다면 전체 문자열이 팰린드롬이 됩니다.
• 위 방법을 이용하여 문제를 해결할 수 있습니다.

1. 주어진 문자열 S를 전체 문자열부터 시작해서 앞에서부터 문자를 하나씩 줄여가며 맨 마지막 문자 하나만 남을 때까지 해당 문자열이 팰린드롬인지 확인합니다.
2. 팰린드롬인지 확인하기 위해 해당 문자열을 시작을 나타내는 start라는 변수와 끝을 나타내는 end라는 변수를 만들고 start가 end보다 커지기 전까지 start는 1씩 늘리고 end는 1씩 줄여가며 start와 end 자리에 있는 문자가 서로 같은지 확인합니다.
3. 만약 두 문자가 서로 달라지는 순간이 생긴다면 해당 문자열은 팰린드롬이 아니게 됩니다.
4. 2,3번 과정을 1번에서 말한 모든 문자열에 대해 순서대로 진행해보고 만약 팰린드롬이 되는 순간이 생긴다면 앞에 줄인 문자만큼의 길이를 주어진 문자열 S의 길이에 더해주면 그것이 가장 짧은 팰린드롬의 길이가 됩니다.