재귀의 귀재

정휘는 후배들이 재귀 함수를 잘 다루는지 확인하려고 재귀 함수와 관련된 문제를 출제하기로 했다.

팰린드롬은 앞에서부터 읽은 것과 뒤에서부터 읽은 것이 같은 문자열이다. 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 함수를 몇 번 호출하는지도 센다.

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

첫째 줄에 테스트케이스의 개수 $T$가 주어진다. ($1 \leq T \leq 1\,000$)

둘째 줄부터 $T$개의 줄에 알파벳 대문자로 구성된 문자열 $S$가 주어진다. ($1 \leq \vert S\vert \leq 1\,000$)

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

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"));
    }
}