[BOJ/JAVA] 1254. 팰린드롬 만들기

AmeriKano·2023년 4월 3일

Java boj 코테연습

문제 링크

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

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

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

입력

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

출력

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

입력 예시

abacaba

출력 예시

접근 방법

가장 짧은 팰린드롬을 어떻게 만들 수 있는지 생각해보면 된다. 주어진 문자열에서 팰린드롬이 되는 부분 문자열 중에서 가장 긴 것을 찾고, 나머지 삭제한 부분을 앞/뒤에 이어붙이면 가장 짧은 팰린드롬이 될 것이다.
문자열을 입력받은 후 팰린드롬인지 아닌지 확인한 뒤, 아니라면 맨 앞 글자를 삭제한 뒤 count 를 증가해준다. (삭제한 문자의 개수) 그 다음 다시 확인하고, 이를 반복하여 팰린드롬이 된다면 삭제한 문자의 수에서 원래 문자열 S 의 길이를 더해주면 최소 길이를 구할 수 있다.

소스 코드

import java.io.*;

public class Main {

    public static boolean checkPalindrome (String s) {
        for (int i=0; i<s.length()/2; i++) {
            if(s.charAt(i) != s.charAt(s.length()-1-i)) return false;
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder S = new StringBuilder(br.readLine());
        int count = 0;
        int original = S.length();

        while (!checkPalindrome(S.toString())) {
            S.deleteCharAt(0);
            count++;
        }
        bw.write((original+count)+"\n");
        bw.flush();
    }
}