소스코드

import sys
input = sys.stdin.readline

def is_palindrome(string, left_idx, right_idx):
    while left_idx < right_idx:
        if string[left_idx] == string[right_idx]:
            left_idx += 1
            right_idx -= 1
        else:
            return False
    
    return True

def is_palindrome_with_cutting(string):
    left_idx = 0
    right_idx = len(string) - 1
    result = 0

    while left_idx < right_idx:
        if string[left_idx] == string[right_idx]:
            left_idx += 1
            right_idx -= 1
        else:
            is_pseudo = is_palindrome(string, left_idx + 1, right_idx) or is_palindrome(string, left_idx, right_idx - 1)
            if is_pseudo:
                result = 1
            else:
                result = 2
            
            break
    
    return result


T = int(input().rstrip())

for _ in range(T):
    string = input().rstrip()
    print(is_palindrome_with_cutting(string))

풀이

1. 최초에 문자열을, 1회용 커터를 하나 들고 팰린드롬 판정을 한다고 생각하자.

2. 일단 양쪽 투 포인터를 좁히면서 팰린드롬인지 판별해나간다. 이 때 투 포인터 위치의 문자가 서로 다르다면, 2갈래의 분기로 나눈다. 일회용 커터로 왼쪽 문자를 없애거나, 오른쪽 문자를 없애거나.

   처리하고 난 두 분기의 문자열에 대해, 단순히 팰린드롬인지 검사만 해주면 된다. 만약 자르고 나서도 서로 다른 문자열이 나오게 된다면, 유사 팰린드롬조차도 아니게 되는 것이다.

   두 분기로 나뉘므로 시간복잡도는 O(2*N) 이다.

어려웠던 점, 배운 점

처음에 이 풀이를 곧바로 생각하지 못하고, 투 포인터로 그리디하게 조건 분기를 많이 해서 문자열을 탐색해나가는 풀이를 작성했었다. 계속 틀려서 다른 사람 테스트케이스를 참고했는데, 그걸 수정하고 나서도 또 다른 케이스를 틀려서 결국 풀이를 갈아 엎고 다시 생각해서 이 풀이를 작성해내어 통과했다.

지나고 보면 참 간단한 풀이였는데.. 역시 어느 한 풀이에 매몰되는게 무서운 것 같다. 처음에는 최대한 여러 접근법을 고안해보고, 그 중에 가장 합리적인 것을 선택해서 풀어본 다음, 막힌다 싶으면 다른 접근법으로 잠깐 넘어가서 생각해보는 식으로 해봐야겠다.