악곱 == 악성곱슬

그리디 알고리즘, 재귀

---

해당 문제는 palindrome을 찾는 문제이다. 다만 1개를 스킵하였을 때 팰린드롬이 가능하다면 해당 경우는 유사 팰린드롬이라 하여 그것도 찾아야 한다.

알고리즘은 다음과 같다.

• 팰린드롬인지 확인하기,
• 아니라면 그 지점부터 start + 1 or end -1 하여 유사 팰린드롬인지 확인하기
• 둘다 아니라면 아무것도 아닌 문자열

내가 겪었던 함정은, start + 1부터 탐색하기에 뒤 문자열을 먼저 스킵했다면 유사팰린드롬이 될 수 있는 경우인데, 이를 판별하지 못하는 아래와 같은 경우이다.

baaba 의 경우 뒤에 a를 스킵하면 유사 팰린드롬이 될 수 있는 경우인데, b를 스킵하면 일반 문자열이 된다.

따라서 아래와 같이 구현했다.

구현

---

import sys

def is_palindrome(string, start, end):
    while start <= end:
        if string[start] == string[end]:
            start, end = start + 1, end - 1
            continue
        else:
            return start, end
    return start, end

def is_pseudo(string, start, end):
    start, end = is_palindrome(string, start, end)
    if start > end:
        return 1
    else:
        return 2

def solution(string):
    start, end = is_palindrome(string, 0, len(string) - 1)
    if start > end:     # 팰린드롬인 경우
        return 0
    else:
        result = is_pseudo(string, start + 1, end)
        if result == 2:
            result = is_pseudo(string, start, end - 1)
        return result

if __name__ == "__main__":
    sys.setrecursionlimit(100000)
    T = int(sys.stdin.readline().rstrip())
    for _ in range(T):
        _str = sys.stdin.readline().rstrip()
        print(solution(_str))