백준 25501번 재귀의 귀재 문제풀이, 파이썬

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

예제 입력 1 복사

5
AAA
ABBA
ABABA
ABCA
PALINDROME

예제 출력 1 복사

1 2
1 3
1 3
0 2
0 1

힌트

Python 3

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

Java 15

public class Main{
    public static int recursion(String s, int l, int r){
        if(l >= r) return 1;
        else if(s.charAt(l) != s.charAt(r)) return 0;
        else return recursion(s, l+1, r-1);
    }
    public static int isPalindrome(String s){
        return recursion(s, 0, s.length()-1);
    }
    public static void main(String[] args){
        System.out.println("ABBA: " + isPalindrome("ABBA"));
        System.out.println("ABC: " + isPalindrome("ABC"));
    }
}

---

 

 

<작성한 코드>

 

#재귀의 귀재
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()
  cnt = 0
  print(isPalindrome(S), cnt)

---

 

<코드 풀이>

 

본 문제에서 우리가 출력해야하는 부분은 isPalindrome 함수의 반환값과 recursion 함수의 호출 횟수.

이렇게 총 두 가지이다. 

 

 

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

함수 isPalindrome에 대한 부분의 코드는 위와 같다.

문제에서 이미 힌트로 제공을 해주었기 때문에, 그대로 사용하면 된다. 

 

 

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)

함수 recursion에 대한 정의 역시 문제에서 이미 제공을 해주었기때문에

이를 동일하게 사용하면 된다. 하지만 우리가 원하는 것은 단순 recursion의 호출이 아니라

이 함수를 총 몇번 호출하게 되는지 그 횟수를 구해야한다. 

그 횟수를 cnt라는 변수를 선언하고, 계속해서 할당할 것인데

global 을 사용하여 cnt를 전역변수로 선언해준다. 

또한, recursion을 호출할 때 마다 cnt 값이 1 증가할 수 있도록 cnt += 1   과 같은 형식으로 작성해주었다. 

 

 

T = int(input())
for _ in range(T):
  S = input()
  cnt = 0
  print(isPalindrome(S), cnt)

 

출력하는 부분은 위와 같다. 

반복문을 돌면서 새로운 입력값을 받을 때마다

cnt = 0 값으로 초기화 해주었다.