BOJ 15927 회문은 회문아니야!
문제 : 주어진 문자열에서 펠린드롬이 아닌 가장 긴 문자열의 길이를 출력하기.
입력 : 문자열이 하나 주어진다. 문자열의 길이는 50만을 넘지 않는다.
출력 : 가장 긴 펠린드롬이 아닌 문자열을 출력한다.
처음에 이 문제를 보고 완전탐색으로 풀어야 하나 했는데, 그렇게 풀면 길이가 50만이기 때문에 모든 문자열을 펠린드롬인지 아닌지 구분하는건 시간 내에 불가능하다고 판단했다.
이 문제는 문제에 허점이 있어 그것을 파고들면되는 '애드 훅' 문제이다.
이 문제의 케이스는 크게 3가지이다.
1 문자열 전체가 펠린드롬이 아닌 경우
- 그냥 문자열의 길이를 출력해주면 된다.
PALINDROME과 같은경우이다.
2 문자열 전체가 펠린드롬이고 모든 문자열이 같은 문자인 경우
- 모든 경우에서 펠린드롬이 되므로 -1을 출력해준다.
ZZZZZZZZZZZZ과 같은경우이다.
3 주어진 문자열이 펠린드롬이지만, 모든 문자열이 같지는 않은 경우
- 왼쪽이나 오른쪽으로 한칸 옮겨주면 그 균형이 깨지게 되므로 전체 문자열의 길이에서 1을 빼서 출력해주면 된다.
ABCBA와 같은 경우이다.
coding chobo