[백준/Python] 25501 재귀의 귀재

[백준/Python] 25501 재귀의 귀재

정답 코드 및 설명

recursion_count = 0

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

def isPalindrome(s):
    global recursion_count
    recursion_count = 0
    
    result = recursion(s, 0, len(s)-1)
    return result, recursion_count

T = int(input())
for _ in range(T):
    S = input()
    result, count = isPalindrome(S)
    print(f"{result} {count}")

1. 팰린드롬인지 아닌지 재귀함수로 확인할 것
2. 재귀함수

• 만약 검사하는 문자열의 길이가 1 이하가 되면 더 이상 비교할 문자가 없으므로 해당 문자열이 팰린드롬으로 간주하고 1을 반환한다.
• 또는, 현재 비교하는 문자 s[1] 과 s[r] 이 서로 다르다면 문자열은 팰린드롬이 아니므로 0을 반환한다.

3. 재귀적 단계
   문자열 양 끝 문자가 같다면 양 끝을 제외한 내부 문자열 s[l+1]에서 s[r-1]까지 팰린드롬인지 아닌지 판별한다.

코드 설명

• 전역 변수 recursion_count를 사용하여 recursion 함수의 호출 횟수를 저장한다
• isPalindrome 함수는 주어진 문자열 s에 대해 팰린드롬 여부를 판별하고, recursion 함수의 호출 횟수와 함께 결과를 반환한다
• 각 테스트 케이스마다 사용자로부터 문자열을 입력받고, 해당 문자열이 팰린드롬인지 아닌지, 그리고 recursion 함수가 몇 번 호출되었는지를 출력한다