[백준] 25501 : 재귀의 귀재 (Python/파이썬)

문제 링크

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

문제

정휘는 후배들이 재귀 함수를 잘 다루는 재귀의 귀재인지 알아보기 위해 재귀 함수와 관련된 
문제를 출제하기로 했다.

팰린드롬이란, 앞에서부터 읽었을 때와 뒤에서부터 읽었을 때가 같은 문자열을 말한다. 
팰린드롬의 예시로 AAA, ABBA, ABABA 등이 있고, 
팰린드롬이 아닌 문자열의 예시로 ABCA, PALINDROME 등이 있다.

어떤 문자열이 팰린드롬인지 판별하는 문제는 재귀 함수를 이용해 쉽게 해결할 수 있다. 
아래 코드의 isPalindrome 함수는 주어진 문자열이 
팰린드롬이면 1, 팰린드롬이 아니면 0을 반환하는 함수다.

#include <stdio.h>
#include <string.h>

int recursion(const char *s, int l, int r){
    if(l >= r) return 1;
    else if(s[l] != s[r]) return 0;
    else return recursion(s, l+1, r-1);
}

int isPalindrome(const char *s){
    return recursion(s, 0, strlen(s)-1);
}

int main(){
    printf("ABBA: %d\\n", isPalindrome("ABBA")); // 1
    printf("ABC: %d\\n", isPalindrome("ABC"));   // 0
}

정휘는 위에 작성된 isPalindrome 함수를 이용하여 어떤 문자열이 팰린드롬인지
여부를 판단하려고 한다.

구체적으로는, 문자열 S를 isPalindrome 함수의 인자로 전달하여 팰린드롬 여부를
반환값으로 알아낼 것이다. 더불어 판별하는 과정에서 recursion 함수를 몇 번 호출하는지 셀 것이다.

정휘를 따라 여러분도 함수의 반환값과 recursion 함수의 호출 횟수를 구해보자.

입력

첫째 줄에 테스트케이스의 개수 T가 주어진다. (1 <=T <=1000)

둘째 줄부터 T개의 줄에 알파벳 대문자로 구성된 문자열 S가 주어진다. (1 <= S <=1000)

출력

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

예제

입력

5
AAA
ABBA
ABABA
ABCA
PALINDROME

출력

1 2
1 3
1 3
0 2
0 1

---

정답 및 풀이

import sys
input = sys.stdin.readline

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):
    return recursion(s, 0, len(s) - 1)

t = int(input())

for _ in range(t):
    s = input().strip()
    cnt = 0
    result = isPalindrome(s)
    print(result, cnt)

1. s = input().strip()
   • sys.stdin.readline()으로 입력받은 문자열에는 개행 문자(\n)가 포함되므로, 이를 제거해 팰린드롬 비교가 정확히 이루어지도록 한다.
2. cnt = 0
   • 재귀 함수가 호출된 횟수를 세기 위한 변수이며, 각 테스트 케이스마다 0으로 초기화한다.
3. def recursion(s, l, r):
   • 문자열 s의 양 끝 인덱스 l, r을 기준으로 팰린드롬 여부를 재귀적으로 검사하는 함수이다.
4. global cnt
   • 재귀 함수 내부에서 호출 횟수 변수 cnt를 증가시키기 위해 전역 변수로 선언한다.
5. cnt += 1
   • recursion 함수가 호출될 때마다 실행되며, 재귀 호출 횟수를 누적한다.
6. if l >= r:
   • 문자열의 가운데에 도달한 경우로, 더 이상 비교할 문자가 없으므로 팰린드롬이 성립하여 1을 반환한다.
7. elif s[l] != s[r]:
   • 양 끝 문자가 서로 다르면 팰린드롬이 아니므로 0을 반환한다.
8. return recursion(s, l + 1, r - 1)
   • 양 끝 문자가 같은 경우, 범위를 한 칸씩 줄여 다음 재귀 호출을 수행한다.
9. def isPalindrome(s):
   • 팰린드롬 검사를 시작하기 위한 진입 함수이다.
10. return recursion(s, 0, len(s) - 1)
    • 문자열의 처음과 끝 인덱스를 기준으로 재귀 검사를 시작한다.
11. t = int(input())
    • 테스트 케이스의 개수를 입력받는다.
12. for _ in range(t):
    • 입력된 테스트 케이스 수만큼 반복하여 팰린드롬 검사를 수행한다.
13. print(result, cnt)
    • 팰린드롬 여부와 재귀 호출 횟수를 문제에서 요구한 형식에 맞게 출력한다.

---

새롭게 배운 내용 및 느낀점

• global
  • 함수 내부에서 함수 밖에 선언된 변수를 수정하고 싶을 때 사용하는 키워