[백준_1254] 팰린드롬 만들기

문제

백준 1254번
https://www.acmicpc.net/problem/1254

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

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

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

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

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

• 예시
  
  • 첫 번째 abab에서 뒤에 a만 추가해준다면 팰린드롬이 되어 기존 str의 길이에서 +1을 해주어 반환한다.
  • 두 번째 abacaba에서 보면 이미 팰린드롬이라 현재 str의 길이를 반환한다.
  • 세 번째 qwerty에서는 첫 문자와 마지막 문자 사이의 공통적인 문자이 없어 마지막 문자인 y을 기준으로 t, r, e, w, q를 추가해주어야 팰린드롬이 완성된다. 그래서 기존 str길이의 추가된 문자의 개수 5를 추가하여 반환한다.

Code

• left = 0이고 right는 str.length - 1로 문자열의 인덱스이다.
• isPalindrome메서드에 넣을 때 str을 문자로 바꿔 arr배열로 넣는다.
• arr[left]와 arr[right]가 같지 않으면 멈춘다.
• 그리고 main에 while문에서 left를 하나씩 늘려준다.
• isPalindrome메서드에 while문에서 arr[left]와 arr[right]가 같다면 left는 하나 늘려주고 right는 하나 줄여준다.
• 서로 같지 않을 때까지 반복하며 left가 right보다 같거나 커질 경우 true를 반환한다.
• main에 while문에서 isPalindrome이 true이면 left에서 str.length(문자열의 길이)를 더해서 break 시켜준다.
  • 여기서 left는 isPalindrome메서드 안에서의 left가 아닌 메서드에 넣을 때 left이다.

Java

import java.util.*;
import java.io.*;


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        String str = st.nextToken(); // 문자열

        int cnt = 0; // 추가된 문자의 개수
        int left = 0;
        while (true) {
            // 팰린드롬 확인
            boolean flag = isPalindrome(left, str.length() - 1, str.toCharArray());
            if (flag) {
                cnt = left + str.length();
                break;
            }
            left++;
        }
        System.out.println(cnt);
    }

    public static boolean isPalindrome(int left, int right, char[] arr) {
        while (left < right) {
            // 같지 않을 경우
            if (arr[left] != arr[right]) {
                break;
            }
            left++;
            right--;
        }

        if (left >= right) {
            return true;
        }
        return false;
    }
}