[BOJ/백준] 25501번. 재귀의 귀재 - C++[cpp]

문제

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

 

시간 초과된 풀이

#include <iostream>
using namespace std;

int count;

int recursion(string s, int l, int r){
    ::count++;
    if(l >= r) return 1;
    else if(s[l] != s[r]) return 0;
    else return recursion(s, l+1, r-1);
}

int isPalindrome(string s){
    return recursion(s, 0, s.length() - 1);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    string temp;
    cin >> n;
    while (n--) {
        ::count = 0;
        cin >> temp;
        cout << isPalindrome(temp) << " " << ::count << '\n';
    }
}

• 함수에서 매개변수 값을 복사하는 시간으로 인해 시간초과 발생

해결 방법 : call-by-reference, 즉 값을 복사하는 것이 아니라, 참조하여 실행 시간을 줄인다

 

#include <iostream>
using namespace std;

int count;

int recursion(string &s, int l, int r){ // 문자열 참조
    ::count++;
    if(l >= r) return 1;
    else if(s[l] != s[r]) return 0;
    else return recursion(s, l+1, r-1);
}

int isPalindrome(string &s){ // 문자열 참조
    return recursion(s, 0, s.length() - 1);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    string temp;
    cin >> n;
    while (n--) {
        ::count = 0;
        cin >> temp;
        cout << isPalindrome(temp) << " " << ::count << '\n';
    }
}