문제
동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다.
동호는 규완이를 위한 깜짝 선물을 준비했다. 동호는 규완이가 적어놓고 간 문자열 S에 0개 이상의 문자를 문자열 뒤에 추가해서 팰린드롬을 만들려고 한다. 동호는 가능하면 가장 짧은 문자열을 만들려고 한다.
동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 최대 50이다.
출력
첫째 줄에 동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력한다.
풀이
- 입력 받은 문자열을 반대로 뒤집은 다음 비교하여 팰린드롬인지 확인 ("abab" -> "baba")
- 팰린드롬이 아니기 때문에 reversePalindrome 실행
- ex) i = 0, split = "b", reverseSplit = "b" -> 팰린드롬이므로 n = 1
i = 1, split = "ba", reverseSplit = "ab" -> 팰린드롬이 아니므로 n 업데이트 X
i = 2, split = "bab", reverseSplit = "bab" -> 팰린드롬이므로 n = 3
i = 3, split = "baba", reverseSplit = "abab" -> 팰린드롬이 아니므로 n 업데이트 X - 입력 받은 문자열의 길이 * 2 - reversePalindrome() = 5
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class No1254_Palindrome {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
System.out.println(palindrome(s));
}
public static int palindrome(String s) {
String reverseStr = new StringBuffer(s).reverse().toString();
// 주어진 문자열이 팰린드롬인지 확인
// 팰린드롬이 아니라면 reversePalindrome을 이용해 값을 얻고
// 팰린드롬이라면 주어진 문자열의 길이를 반환
if (!s.equals(reverseStr)) {
return s.length() * 2 - reversePalindrome(reverseStr);
} else {
return s.length();
}
}
public static int reversePalindrome(String s) {
int n = 0; // 팰린드롬을 만들 수 이쓴 문자열 길이를 담을 변수
// 한 글자씩 더해가면서 팰린드롬을 만들 수 있는 최대 길이를 구한다.
for (int i = 0; i < s.length(); i++) {
String split = s.substring(0, i);
String reverseSplit = new StringBuffer(split).reverse().toString();
if (split.equals(reverseSplit)) {
n = split.length();
}
}
return n;
}
}
'백준' 카테고리의 다른 글
[백준 11047번][Java][Greedy] 동전 0 (0) | 2023.04.03 |
---|---|
[백준 2003번][Java][투 포인터] 수들의 합 2 (0) | 2023.04.03 |
[백준 2167번][Java][2차원배열][DP] 2차원 배열의 합 (0) | 2023.04.03 |
[백준 11725번][Java][Tree][DFS] 트리의 부모 찾기 (0) | 2023.03.27 |
[백준 5613번][Java] 계산기 프로그램 (0) | 2023.03.27 |