[백준/BOJ] 팰린드롬 만들기 (Java)

[백준/BOJ] 팰린드롬 만들기

[풀이]

주어진 문자열의 뒤에 문자를 추가해서 팰린드롬이 될 때, 만들어진 문자열의 최소 길이를 구하는 문제입니다.

 

주어진 예제 입력의 경우 "abab" 뒤에 'a'를 추가하면 "ababa"로 팰린드롬이 만들어짐을 확인할 수 있습니다.

 

s = "ABDCEC"가 주어진다면 우선 s가 팰린드롬인지 확인한 후 s가 팰린드롬이 아니라면 아래 과정을 따른다.

 

1) s의 첫 글자를 반대편에 이어 붙인 후 팰린드롬을 확인한다 => 실패

2) s의 두 문자를 반대편에 역순으로 이어 붙인다 => 실패

 

위 과정을 문자열 s에 대해 반복하면 팰린드롬 문자가 만들어지는 경우를 찾을 수 있고 이때 문자열의 길이를 출력하면 된다.

수행 과정

package baekjoon;
import java.util.*;
public class BOJ_1254_팰린드롬만들기 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        
        if(check(s)) // 팰린드롬 O
            System.out.println(s.length());
        else { // 팰린드롬 X
            for(int i=0; i<s.length(); i++) {
                String temp = s; 
                for(int j=i; j>=0; j--)
                    temp += String.valueOf(s.charAt(j));
                /**
                 * s가 "abacec 일 때,
                 * abacec a
                 * abacec ba
                 * abacec aba 
                 * 위와 같이 s의 앞에서부터 반대로 이어 붙이면서 팰린드롬 체크를 수행한다
                 */
                if(check(temp)) {
                    System.out.println(temp.length());
                    break;
                }
            }
        }
        sc.close();
    }
    
    // check palindrome
    static boolean check(String s) {
        int l = 0;
        int r = s.length()-1;
        while(l<r) {
            if(s.charAt(l) != s.charAt(r))
                return false;
            l++;
            r--;
        }
        return true;
    }
}