[백준] 재귀 - 25501번 (Python)

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

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 함수의 호출 횟수를 한 줄에 공백으로 구분하여 출력한다.

코드 정답

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)

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

풀이

팰린드롬의 문자열인지, 아닌지를 판단하는 문제이다. 팰린드롬이란 쉽게 말하여 첫 번째와 마지막이 같고, 두 번째와 (마지막-1) .. 처럼 앞에서부터 1칸씩 앞으로, 뒤에서부터 1칸씩 뒤로 가는데 중앙값까지 도착할 때 완전히 같은 것을 말한다.

 

1~2행 : 일반적으로 input 을 사용하게 된다면 시간 초과가 나올 수 있다. 그렇기 때문에 input 과 같으면서도 빠른 sys.stdin.readline 을 사용하기 위해 import sys 란 헤더를 선언해주었고 input 에 sys.stdin.readline 을 대입하여 input 을 sys.stdin.readline 처럼 사용 할 수 있게끔 된다.

import sys
input = sys.stdin.readline

4~10행 : 13행에서 보낸 값을 각각 s, l, r 로 받는다. 이후 cnt 라는 변수를 선언해주는데, 함수 뿐만 아니라 어디서든 사용할 수 있게끔 하기 위해 global 전역 변수로 선언을 해준다. 이후 cnt 의 값을 해당 함수가 사용 될 때마다 1씩 증가하게끔 만들어주었다.

만약에 l 의 값이 r 보다 크거나 같으면 1 을 리턴시킨다. 그런다면 cnt 의 출력 값은 1이 된다.

만약 s[l] 과 s[r] 즉, 비교하는 값이 다르다면 0을 리턴시킨다. cnt 의 출력 값이 0이 된다.

위의 두 가지의 경우가 아니라면 recursion() 함수에 l+1과 r-1을 한 값을 전달하여 재귀함수를 실행해준다.

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)

12~13행 : 17행에서 보내진 값의 변수명을 s 라고 선언을 한다. 이후 recursion() 함수에 s, 0, len(s)-1 을 각각 보내며 돌아온 값을 return 시킨다.

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

15~17행 : 입력받은 값의 만큼 반복이 된다. cnt 란 변수를 생성하고 0이란 값을 넣어주었고, isPalindrome() 함수에 입력받은 값을 넣어주는데, rstrip() 을 이용해 오른쪽 끝의 공백을 제거해주었다. 이후 return 이 되어 돌아온 값을 출력한다.

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