[Python] 백준 17609번 - 회문

📖 문제

17609번: 회문

 

🔎 풀이

투 포인터와 재귀를 이용하여 해결하였습니다. 문제는 단순히 회문만 판별하는 것이 아니라, 한 문자를 삭제했을 때 회문이 되는 경우도 판별해야 합니다. 투 포인터로 탐색하다 두 문자가 다른 경우, 왼쪽 포인터만 혹은 오른쪽 포인터만 옮기는 경우의 수 2가지가 생깁니다. 2가지 경우의 수 중, 더 좋은 결과값을 최종 결과로 반환하면 됩니다.

 

💻 코드

import sys
input=sys.stdin.readline


def palindrome(string, i, j, chance):
    while i < j:
        if string[i] != string[j]:
            # 기회가 남아 있는 경우, 왼쪽 포인터를 옮기는 경우와 오른쪽 포인터를 옮기는 경우로 분기
            if chance:
                return min(palindrome(string, i+1, j, chance-1), palindrome(string, i, j-1, chance-1))
            return 2

        i += 1
        j -= 1
    
    # 기회가 남아있다면 0, 이미 사용했다면 1
    return 0 if chance else 1


T = int(input())
for _ in range(T):
    string = input().rstrip()
    print(palindrome(string, 0, len(string)-1, 1))