백준[15927] - 회문은 회문아니야!!

• 문제: https://www.acmicpc.net/problem/15927
• 분류: 문자열
• 난이도: G5
• 소요시간: 10m
• 자아성찰:
  • 문자열,, 분류의 문제라기보단 팰린드롬의 성질을 알면 쉽게 풀 수 있는 문제가 아니었을까 싶다.
  • 시간복잡도는 문자열의 길이 <= 50만이므로 O(len / 2) = 25만 정도이다.
  • 문자열의 처음과 끝에서 각 문자를 chatAt()을 통해 비교하며 각 케이스를 확인한다.
  • 3가지 케이스로 결과가 나누어지며, 답은 len, len - 1, -1 셋 중 하나로만 떨어진다.
    • 1 - 문자열 자체가 팰린드롬이 아님 (ABCDE) : len
    • 2 - 문자열 자체가 팰린드롬이면서 모두 같은 문자임 (AAAAA) : -1
    • 3 - 문자열 자체가 팰린드롬이면서 다른 문자임 (ABCBA) : len - 1
  • 1의 경우에는 문자열 자체가 팰린드롬이 아니므로 len이 정답이다.
  • 2의 경우에는 모든 문자열이 같은 문자이므로 모든 부분 문자열도 팰린드롬이다.
  • 3에서 팰린드롬의 성질이 중요한데, 문자열 자체가 팰린드롬이고 모두 같은 문자가 아닐 때, 문자 하나를 제거하면 팰린드롬이 아니게 되므로 len - 1이다.

15927번: 회문은 회문아니야!!

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B_15927 {

    public static String s;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        s = br.readLine();
        // 문자열의 모든 문자가 같은지
        boolean isAllSame = true;
        int len = s.length();
        for (int i = 0; i < len / 2; i++) {
            // 각 위치의 L, R 문자 비교.
            // 다르다면 문자열 자체는 팰린드롬이 아니므로 len이 정답 
            if (s.charAt(i) != s.charAt(len - i - 1)) {
                System.out.println(len);
                return;
            }
            // 현재 문자와 다음 문자가 다르다면 문자열의 모든 문자가 같지 않음
            if (s.charAt(i) != s.charAt(i + 1)) {
                isAllSame = false;
            }
        }
        // 모든 문자열의 문자가 같다면 모든 부분 문자열은 팰린드롬
        if (isAllSame) {
            System.out.println(-1);
        } else {
            // 문자열 자체는 팰린드롬 && 문자가 다르다면 문자 하나를 제외한 문자열은 팰린드롬. len - 1
            System.out.println(len - 1);
        }
    }
}