[Python] 백준 25501 재귀의 귀재

문제 분석

• 펠린드롬 : 대칭을 이루는 문자열 ex) AAA, ABBA, ABABA
• 주어진 코드는 문자열이 펠린드롬인지 여부를 판단하는 함수가 구현된 코드
• 코드에서 펠린드롬인지 판별하는 과정에서 재귀함수를 몇 번 호출하는가
• 함수의 반환값과 재귀함수의 호출 횟수 구하기
• 맞으면 1, 아니면 0 

 

코드 설계

• t : test case  (1 ≤ t ≤ 1000)
• s : 펠리느롬 문자열인지 확인할 문자  (1 ≤ |S| ≤ 1000)
• 출력 : 각 test case 마다 반환값 & 함수를 호출한 횟수를 공백으로 구분하여 출력

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

• 문자열, 문자열 길이

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

• 만약 l >= r 즉, 0보다 문자열의 길이-1 이 더 작은 경우 (예를 들면 아무것도 입력 x) return 1
• s[l] != s[r] 즉 대칭이 아니면 return 0
• ~ 종료조건

어떻게 호출 횟수를 계산할 수 있을까?

 

정답 코드

1차

import sys

t = int(sys.stdin.readline().rstrip())

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

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


for _ in range(t) :
    cnt = 0
    s = sys.stdin.readline().rstrip()
    result, count = isPalindrome(s)
    print(result, count)

 

다른 풀이

import sys

input = sys.stdin.readline


def recursion(s, l, r):
    global cnt  # 함수 내에서 전역 변수로 cnt를 활용하기 위해 global로 명시해준다.
    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):
    return recursion(s, 0, len(s) - 1)


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