[백준 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$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

 

힌트(파이썬)

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'))

 

---

 

풀이

이 문제는 힌트에 재귀함수는 다 나와있어서 그대로 사용하면 됩니다.

그리고 출력만 수정해서 함수 반환값과 함수의 호출 횟수를 출력 해야합니다.

입력에 따른 함수 반환값
입력에 sys 함수를 사용했기 때문에 .rstrip()을 사용해 줘야합니다.
sys함수는 입력이 되면 마지막에 줄바꿈이 자동으로 입력이 되기 때문에
오른쪽 공백을 지워주는 .rstrip()을 사용

전역변수를 이용한 카운트 변수
recursion함수의 호출 횟수를 구해야 되는데요.
함수 안에 변수를 생성하면 지역변수로 인해 함수를 벗어나면 변수가 사라집니다.
그렇기 때문에 전역변수(global)를 사용해서 함수 밖에서도 사용 가능하게 해줍니다.

코드를 순서대로 작성한다면
1. 힌트의 코드를 수정
2. 주어지는 숫자만큼 문자 입력
3. sys입력 부분을 수정
4. 전역변수를 사용해서 함수를 몇 번 사용했는지 카운트

---

작성 코드

import sys
input = sys.stdin.readline # 입력 시간초과를 방지하기 위해 input을 sys함수로 대체

def recursion(s, l, r):
    global cnt # 전역변수 : 함수 밖에서도 사용가능
    cnt += 1 # 함수가 호출 될 때마다 +1

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

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

N = int(input())

for _ in range(N):
    cnt = 0 # 하나씩 확인 할 때마다 0으로 초기화
    print(isPalindrome(input().rstrip()), cnt) # .rstrip()을 사용해서 sys함수의 줄바꿈을 삭제