[Java] 백준 1254번 : 팰린드롬 만들기

문제

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다.

동호는 규완이를 위한 깜짝 선물을 준비했다. 동호는 규완이가 적어놓고 간 문자열 S에 0개 이상의 문자를 문자열 뒤에 추가해서 팰린드롬을 만들려고 한다. 동호는 가능하면 가장 짧은 문자열을 만들려고 한다.

동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 최대 50이다.

출력

첫째 줄에 동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력한다.

예제 입력 1

abab

예제 출력 1

5

예제 입력 2

abacaba

예제 출력 2

7

예제 입력 3

qwerty

예제 출력 3

11

예제 입력 4

abdfhdyrbdbsdfghjkllkjhgfds

예제 출력 4

38

 

소스코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	private static String S=null;
	private static List<Integer> even=new ArrayList<>();	// 길이가 짝수인 팰린드롬 검사
	private static List<Integer> odd=new ArrayList<>();	// 길이가 홀수인 팰린드롬 검사
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		S=sc.next();
		int len=S.length();
		int result=0;
        
        if(len==1) result=1;	// 문자열 길이가 1인 경우
        else {	// 문자열 길이가 2이상인 경우
            for(int i=len/2;i<len;i++) {	// 문자열 뒤에만 문자 추가가 가능하므로 문자열 길이의 절반 지점부터 팰린드롬 검사
			    if(S.charAt(i-1)==S.charAt(i)) {
				    even.add(i);
			    }
                if(i<len-1 && S.charAt(i-1)==S.charAt(i+1)) {
				    odd.add(i);
			    }
            }
            
            int cnt=0;
			int maxCnt=0;
			if(even.size()==0 && odd.size()==0) {	// 팰린드롬이 가능한 영역이 없으면 현재 문자열에서 0~len-1까지를 뒤집어서 붙여짐
				result=len+len-1;
			} else {
				for(int i=0;i<even.size();i++) {	// 길이가 짝수인 팰린드롬 검사
					int now=even.get(i);
	                for(int j=now;j<len;j++) {
	                    if(now-1>=0 && S.charAt(now-1)==S.charAt(j)) {
	                        cnt+=2;
	                        now--;
	                    } else {
	                        cnt=0;
	                        break;
	                    }
	                }
					if(cnt>maxCnt) {	// 팰린드롬이 가능한 최대 길이 조사
						maxCnt=cnt;
					}
					cnt=0;
				}
				for(int i=0;i<odd.size();i++) {	// 길이가 홀수인 팰린드롬 검사
					cnt=1;
					int now=odd.get(i);
	                for(int j=now+1;j<len;j++) {
	                    if(now-1>=0 && S.charAt(now-1)==S.charAt(j)) {
	                        cnt+=2;
	                        now--;
	                    } else {
	                        cnt=0;
	                        break;
	                    }
	                }
					if(cnt>maxCnt) {	// 팰린드롬이 가능한 최대 길이 조사
						maxCnt=cnt;
					}
					cnt=0;
				}
				if(maxCnt==0) result=len+len-1;
				else result=len+len-maxCnt;
			}
        }
		System.out.println(result);
	}
}