문제
동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다.
동호는 규완이를 위한 깜짝 선물을 준비했다. 동호는 규완이가 적어놓고 간 문자열 S에 0개 이상의 문자를 문자열 뒤에 추가해서 팰린드롬을 만들려고 한다. 동호는 가능하면 가장 짧은 문자열을 만들려고 한다.
동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 최대 50이다.
출력
첫째 줄에 동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력한다.
나의 풀이
어떻게 풀어야 할지 감도 안 잡혀서 다른 사람의 풀이를 참고했습니다.
문자열의 어느 지점부터 끝까지의 부분 문자열이 팰린드롬인지를 차례대로 확인해가면서, 가장 빠르게 팰린드롬이 되는 지점을 찾습니다. 그런 다음, 그 앞부분만 뒤에 붙이면 전체 문자열이 팰린드롬이 됩니다.
예를 들어, 문자열 ababc가 있을 때:
ababc -> 팰린드롬 x
babc -> 팰린드롬 x
abc -> 팰린드롬 x
bc -> 팰린드롬 x
c -> 팰린드롬 o
c가 팰린드롬이므로, 그 앞의 abab를 반대로 뒤에 붙이면 ababcbaba → 팰린드롬 완성
따라서 전체 길이는 원래 길이 + 붙이는 문자 수 = 5 + 4 = 9
나의 코드
import java.io.*;
/**
* 백준 1254 팰린드롬 만들기 (실버 2) - 문자열
* <a href="https://www.acmicpc.net/problem/1254">...</a>
*/
public class Main {
private static boolean isPalindrome(String s) {
int start = 0;
int end = s.length() - 1;
while(start <= end) {
if (s.charAt(start) != s.charAt(end)) return false;
start++;
end--;
}
return true;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s= br.readLine();
int answer = s.length();
for (int i = 0; i < s.length(); i++) {
if(isPalindrome(s.substring(i))) {
break;
}
answer++;
}
System.out.println(answer);
}
}