[C++] 백준 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≤�≤1000$1 \leq T \leq 1\,000$)

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

- 출력

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

 

- 예제

//INPUT//
5
AAA
ABBA
ABABA
ABCA
PALINDROME

//OUTPUT//
1 2
1 3
1 3
0 2
0 1

 

 

 

---

 

 

- 구상

이미 코드가 구현되어 있으니, recursion 등에 대한 해석만 진행하겠다. 함수 호출 횟수는 직전 포스트에서 사용한 전역변수를 활용한 방식을 사용할 것이다.

 

➡ recursion은 주어진 문자열이 회문(앞으로 읽나 뒤로 읽나 똑같은 문자열)임을 판별해주는 데에 쓰인다.

 

➡ 따라서 맨 앞 맨 뒤가 같으면 앞에서 두 번째, 뒤에서 두 번째 문자가 동일한 지 판별하는 식으로 회문인 지 아닌 지를 판별해주는 방식이다.

 

 

 

---

 

 

- 구현

printf 안에 cnt도 넣어서 한 줄로 코드를 끝내고 싶었지만, isPalindrome()이 끝난 뒤에 cnt의 값이 변하기에, 다른 줄로 설정해주었다.

#include <iostream>
#include <vector>
#include <stdio.h>
#include <cstring> //C++에서는 cstring을 사용해서, strlen()을 구동시킨다.
using namespace std;

int cnt;

int recursion(const char* s, int l, int r) {
    cnt++;
    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() {
    int T;
    cin >> T;
    vector<string> Ss(T);
    for (int i = 0; i < T; i++)
        cin >> Ss[i];

    cnt = 0;

    for (int i = 0; i < T; i++) {
        printf("%d ", isPalindrome(Ss[i].c_str())); //printf() : studio.h를 include한 덕에 사용 가능. c_str() : cstring을 include한 덕에 사용 가능.(string을 const char*로 바꿔주는 함수)
        cout << cnt <<endl;
        cnt = 0;
    }

    return 0;
}