문제
팰린드롬이란 앞으로 읽으나 뒤로 읽으나 같은 문자열을 말한다. 팰린드롬의 예시로 POP, ABBA 등이 있고, 팰린드롬이 아닌 것의 예시로 ABCA, PALINDROME 등이 있다.
같은 의미를 가지는 여러 단어들을 보자.
- 회문 (한국어)
- palindrome (영어, 프랑스어, 노르웨이어, 그리스어, 라틴어)
- 回文 (일본어, 중국어)
- palindrom (독일어, 덴마크어)
- palindromi (핀란드어)
- palíndromo (스페인어, 포르투갈어)
- palindromo (이탈리아어, 에스페란토어)
- палиндром (러시아어)
- قلب مستو (아랍어)
뭔가 이상한 점이 보이지 않는가? 그 어떤 언어에서도 팰린드롬을 뜻하는 단어는 팰린드롬이 아니다! 많은 사람들이 추구하는 “대칭의 아름다움”은 그저 허상에 불과하다.
알파벳 대문자로 이루어진 문자열이 주어졌을 때, 팰린드롬이 아닌 가장 긴 부분문자열의 길이를 구해 보자. 이때 부분문자열을 이루는 글자는 연속해야 한다. AB는 ABCD의 부분문자열이지만, AC는 아니다.
입력
길이가 1 이상 50만 이하인 문자열이 주어진다.
출력
팰린드롬이 아닌 가장 긴 부분문자열의 길이를 출력한다. 그런 부분문자열이 없으면 -1을 출력한다.
예제 입력 1
ABCBA예제 출력 1
4예제 입력 2
PALINDROME예제 출력 2
10예제 입력 3
ZZZ예제 출력 3
-1풀이
이 문제는 특별한 알고리즘을 이용해서 풀진 않았다. 이 문제에서 나오는 결과는 3가지이다. 전체 문자열에서 대칭위치의 문자가 한 문자라도 다르면 문자열의 길이가 최대값이고 회문인 경우 모든문자가 같은문자라면 부분 문자열은 모두 회문, 모든 문자가 같은 문자가 아니라면 전체 문자열 길이의 -1한 값이 최대이다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
boolean flag = false;
int len = input.length();
for (int i=0; i<len/2; i++) {
if (input.charAt(i) != input.charAt(len-i-1)) { //한글자라도 다르면 문자열 길이가 답
System.out.println(len);
return;
}
else if (input.charAt(i) != input.charAt(i+1)) //모든 글자가 같은 글자인지 판별
flag = true;
}
if(flag) //회문인경우 한글자만 짧아지면 회문이 아니게 됨
System.out.println(len-1);
else //회문인 경우 문자가 모두 같으면 부분문자열도 모두 회문
System.out.println(-1);
}
}
👶🏻Jr. Programmer