[백준] 25501 | 재귀의 귀재 [파이썬/python]

문제

link: https://www.acmicpc.net/problem/25501

문자열의 팰린드롬 여부와 팰린드롬 여부를 확인하기 위해 재귀함수를 호출한 횟수를 출력하는 문제이다.

(C, python, JAVA의 경우 문제 페이지에서 팰린드롬 여부를 확인하기 위한 함수 코드를 제공하고 있기 때문에 복사해서 이용할 수 있다.)

 

접근

본문에 제시된 함수에 재귀함수 호출 횟수를 확인하기 위한 변수 cnt를 추가하여 문제를 해결했다.

 

코드

import sys
input = sys.stdin.readline

def recursion(s, l, r, cnt):
    cnt += 1
    if l >= r: return 1, cnt
    elif s[l] != s[r]: return 0, cnt
    else: return recursion(s, l+1, r-1, cnt)

def isPalindrome(s):
    return recursion(s, 0, len(s)-1, cnt)

T = int(input())

for _ in range(T):
    S = input().rstrip()
    cnt = 0
    isP, cnt = isPalindrome(S)
    print(isP, cnt)