백준 25501 - 재귀의 귀재 (python)

문제

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

25501번: 재귀의 귀재

 

풀이

문제에서 팰린드롬 여부를 판단하는 험수가 미리 작성되어 있으므로 이 코드를 이용하여 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'))

해당 코드의 동작 방식을 보면

1. recursion함수는 문자열(s)과 정수(l, r)을 입력받아 s의 l번째와 r번째 글자를 비교한다.

2. 비교한 두 문자가 다르면 0을 반환하고 반복을 중단하고, 비교한 문자열이 다르면 l+1, r-1로 recursion함수를 다시 실행한다.

3. 모든 글자를 비교하면 1을 반환하고 반복을 중단한다.

 

실행 횟수를 저장할 전역변수를 선언하고, recursion함수가 실행 될 때 마다 1씩 더해 준 후 출력하면 된다.

 

프로그램을 완성하면 아래와 같다.

count = 0 #호출 횟수를 저장 할 변수 선언
def recursion(s, l, r):
    global count #전역변수 사용을 위해 global 사용
    count += 1 #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 count #전역변수 사용을 위해 global 사용
    count = 0 #count 변수 초기화
    return recursion(s, 0, len(s)-1)


T = int(input())
for i in range(T):
    S = input() 
    print(isPalindrome(S),count)