[백준][C++] 25501번 : 재귀의 귀재

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

25501번: 재귀의 귀재

---

- 문제

 

  문제에서 주어진 함수를 그대로 만들어서 사용하면 된다.

 

---

- 해설

 

  문제에서 주어진 recursion 함수에서 return을 1이랑 0을 하지 말고 l+1하면 된다.

 

원래 1이어야 할 곳에 l+1을 해서 몇번 recursion되었는지 확인하고,

 

0이어야 할 곳에는 -(l+1)을 해서 이게 0이라는 것을 표현하면 된다.

 

 

---

- 풀이

#include <iostream>
#include <string.h>

using namespace std;

int recursion(const char *s, int l, int r)
{
    if (l >= r)
        return (l + 1);
    else if (s[l] != s[r])
        return -(l + 1);
    else
        return recursion(s, l + 1, r - 1);
}

int isPalindrome(const char *s)
{
    return recursion(s, 0, strlen(s) - 1);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    char s[1001];
    int T;
    int temp;
    cin >> T;
    for (int i = 0; i < T; i++)
    {
        cin >> s;
        temp = isPalindrome(s);
        if (temp > 0)
        {
            cout << "1 " << temp << endl;
        }
        else
        {
            cout << "0 " << -temp << endl;
        }
    }
    return 0;
}

 

---

- 새롭게 알게 된 점

 

생각보다 string이 시간복잡도가 큰 걸 알 수 있다. char s[1001] 만들었을 때는 성공하는데, 쉽게 가려고 string을 사용하니 시간초과가 났다.

 

----- string 시간 복잡도 큼!!!!