[Baekjoon] 1254번 - 팰린드롬 만들기(JAVA)

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

조건 체크

"문자열 S로 만들 수 있는 가장 짧은 문자열" 을 만들어야 하고, 앞에서 읽으나 뒤에서부터 읽으나 같은 문자열이어야 한다.

예를들면 토마토 같은...

예제에서 주어진 간단한 식에는 abab => ababa 등의 형태로 가운데 문자 a를 기준으로 ab, ba가 있는 형태도 있지만, abba도 팰린드롬이다.

풀이

입력으로 주어진 S가 팰린드롬인지부터 확인하고, 팰린드롬으로 만들 수 있는지 체크하도록 한다.

예를들어 abcdefghi라는 입력이 왔을때, 문자열 길이는 9이므로, (팰린드롬의 최대길이는 입력 문자열 S*2 이다.)

for문을 9/2 q부터 9까지 반복문을 통해 찾으면 된다.

S = abcdefghi 일때, S에서 9/2(4.5인데 int이므로 4가 출력) substring을 추출해 'abcd' 형태로 만들고 StringBuffer를 통해 reverse 한 후 연결한다.

그럼 첫번째 팰린드롬을 체크할 문자열은 'abcddcba'이고 S가 포함되는지 체크,

같은방법으로 두번째는 abcdedcba, abcdeedcba, abcdefedcba, abcdeffedcba, ... 순으로 abcdefghiihgfedcba 까지 체크하면 끝이다.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String N = br.readLine();
        String a = N.substring(0, N.length()/2), b = N.substring(N.length()/2, N.length()), c, d;
        for(int i = 0; i < b.length(); i++) {
            String t = new StringBuffer(a).reverse().toString();
            c = a + t;
            d = a + b.charAt(i) + t;
            if(c.contains(N)) {
                System.out.println(c.length());
                break;
            }
            if(d.contains(N)) {
                System.out.println(d.length());
                break;
            }
            a+=b.charAt(i);
        }
    }
}