문제
문자열 S가 주어졌을 때, S의 부분 문자열 중 회문이 아닌 가장 긴 부분 문자열의 길이를 구하는 프로그램을 작성하시오.
부분 문자열이란 S에서 연속된 문자들의 집합이다.
입력
첫째 줄에 문자열 S가 주어진다. S의 길이는 1 이상 5,000,000 이하이다.
문자열은 대문자 알파벳으로만 이루어져 있다.
출력
S의 부분 문자열 중 회문이 아닌 가장 긴 부분 문자열의 길이를 출력한다. 그런 부분 문자열이 없으면 -1을 출력한다.
예제
입력 1
ABBA출력 1
3입력 2
AAAAAA출력 2
-1풀이
핵심 아이디어: 전체 문자열이 회문이 아니면 길이 N이 정답이다. 전체가 회문이면 한 글자를 제거한 N-1이 정답이다. 단, 모든 문자가 같은 경우(예: "AAAA")는 어떤 부분 문자열도 회문이 되므로 -1을 출력해야 한다.
- 먼저 모든 문자가 동일한지 확인한다. 첫 번째 문자와 다른 문자가 하나도 없으면 -1을 출력하고 종료한다.
- 전체 문자열 S가 회문인지 확인한다.
- 회문이 아니면 → 전체 길이 N을 출력한다.
- 회문이면 → 첫 글자 또는 마지막 글자를 제거한 부분 문자열(
S[1..N-1]또는S[0..N-2])은 반드시 회문이 아님이 보장된다. 따라서N-1을 출력한다.
핵심은 "전체 문자열이 회문인 경우, 한 끝을 잘라낸 문자열은 회문이 될 수 없다"는 점이다. 단, 모든 문자가 같은 경우는 잘라낸 문자열도 회문이 되므로 별도로 처리해야 한다.
코드
package day399;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Day351BOJ15927회문아닌 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
char c = s.charAt(0);
int i = 1;
for (; i < s.length(); i++) {
if (c != s.charAt(i))
break;
}
if (i == s.length()) {
System.out.println(-1);
return;
}
i = 0;
for (; i < s.length() / 2; i++) {
if (s.charAt(i) != s.charAt(s.length() - 1 - i))
break;
}
System.out.println(i == s.length() / 2 ? s.length() - 1 : s.length());
}
}복잡도
- 시간: O(N) — 문자열을 최대 2번 선형 순회
- 공간: O(N) — 입력 문자열 저장