백준 25501번: 재귀의 귀재 python

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

문제 요약

문제 요약

문자열이 팰린드롬인지 재귀 함수로 판별하고, 재귀 함수가 몇 번 호출되었는지도 함께 출력하는 문제.

팰린드롬이란?
앞에서 읽으나 뒤에서 읽으나 같은 문자열
예: "ABBA", "ABABA"

문제에서는 팰린드롬 여부를 판단하는 함수가 이미 제공되어 있고, 이를 기반으로 isPalindrome() 함수의 반환값과 recursion() 함수의 호출 횟수를 출력해야 한다.

아래 코드가 문제에서 제공 된 isPalindrome함수이다:

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

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

print('ABBA:', isPalindrome('ABBA'))
print('ABC:', isPalindrome('ABC'))

우선 코드를 뜯어보자면
recursion함수는 s, l, r 으로 세개의 파라미터를 받는데
1. l이 보다 크거나 같으면 1을 반환,
2. s의 l번째 인덱스의 값이 s의 r번째 인덱스값과 같지 않다면 0반환
3. 둘다 조건을 만족하지 않는다면 recursion 함수를 l은 1증가시키고, r은 1 감소시켜서 재귀호출한다.

isPalindrome 함수는 s를 인자로 받고,
recursion함수를 리턴하는데 (tmi : 함수를 리턴하는 함수를 고차함수라고 한다) 이때 recursion 함수의 들어가는 인자는 s, 0, 그리고 s의 길이 -1 이다.

이것의 의미는 l = 0 이 되고, r은 len(s)-1 이므로 인덱스의 들어가게된다면 s의 마지막 자리 요소를 의미하게 된다.

예시

isPalindrome('ABBA') 는 다음과 같이 호출된다.
recursion('ABBA',0,len('ABBA')-1)
는 즉
recursion('ABBA',0,3) 로 호출되므로
첫번째 조건식 0>=3이 아니므로 다음 조건식
s[0] != s[3] 는 A != A 가되며 조건이 만족하지않으므로
recursion(s, 0+1, 3-1) = recursion(s, 1, 2) 가 호출된다.
이는 다시

recursion('ABBA',1, 2) 가 되고
1>=2 가 아니므로 두번째 조건식,
s[1] != s[2] 에서 B != B 가 아니므로
recursion(s,1+1, 2-1) 가 되며 recursion(s,2,1) 이된다.
이는 첫번째 조건식에서 2>=1 가되며 1이 반환된다.

즉 팔린드롬 이면 1, 아니면 0이 나오는 함수이다.

이제 함수를 이해했으니 문제에서 원하는 값을 보자.

입력

테스트 케이스 수 T , 대문자 문자열 S

출력

각 테스트케이스마다, isPalindrome 함수의 반환값과 recursion 함수의 호출 횟수를 한 줄에 공백으로 구분하여 출력한다.

즉 문제는 isPalindrome의 함수를 이해하고, 힌트의 함수를 이용하여 Palindrome함수의 반환값과 recursion함수의 호출횟수를 출력해주면 된다.

Palindrome의 반환값은 단지 print 함수에 넣어주면 됐고, recursion의 호출 횟수를 전역변수 cnt를 선언해주고 담아준뒤 출력해줬다.

내 해답

import sys

cnt= 0 ;

def recursion(s, l, r):
    global cnt
    cnt += 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 cnt 
    cnt = 0 
    return recursion(s, 0, len(s)-1)

T = int(sys.stdin.readline())

for _ in range(T):
    S = sys.stdin.readline().rstrip()
    print(isPalindrome(S), cnt)