[BOJ] 25501 재귀의 귀재

1. 기본 풀이

---

이 문제는 사실 브론즈2 밖에 안되는 굉장히 쉬운 문제다. 당장 재귀 코드도 다주기 때문에 그대로 풀면 된다.

 #include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
using namespace std;

int cnt;

int recursion(const string 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 string s){
    return recursion(s, 0, s.size()-1);
}

int main(){
    fastio;
    int t;
    cin >> t;
    for(int i = 0; i < t; i++) {
        cnt = 0;
        string s;
        cin >> s;
        cout << isPalindrome(s) << ' ' << cnt << endl;
    }
    return 0;
}

그러나 이대로 풀면 바로 TLE가 나온다. 그렇다면 어떻게 풀어야 될까?

 

2. 맞왜틀?

---

이는 c++의 string 타입의 특성에 의한 것이다.

string은 문자열을 함수 인자로 넘겨줄 때 문자열을 통째로 넘겨주기 때문에 시간이 오래걸리지만, char *는 문자열을 넘겨줄 때 시작주소만을 넘겨주기 때문에 string보다 더 빠르다.

이를 해결하는 방법은 총 2가지가 있다.

1. char *사용

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
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(){
    fastio;
    int t;
    cin >> t;
    for(int i = 0; i < t; i++) {
        cnt = 0;
        char s[1001];
        cin >> s;
        cout << isPalindrome(s) << ' ' << cnt << endl;
    }
    return 0;
}

이렇게 string대신 char *로 풀면 된다.

 

2. s.c_str()사용

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
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(){
    fastio;
    int t;
    cin >> t;
    for(int i = 0; i < t; i++) {
        cnt = 0;
        string s;
        cin >> s;
        cout << isPalindrome(s.c_str()) << ' ' << cnt << endl;
    }
    return 0;
}

 사실상 이 포스트를 작성한 실질적인 이유인데, std::string c_str()함수를 사용하면 string형이 char *형으로 변환된다. 이를 활용하면 기존에 string타입에서는 사용할 수 없었던 strtok, strlen 등 string.h에 포함되어있는 여러 함수들을 사용할 수 있게된다.

 

 이는 잘 사용한다면 큰 도움이 될 것 같다.