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에 포함되어있는 여러 함수들을 사용할 수 있게된다.

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

 +와 -만을 이용한 식을 입력받아 괄호를 적절히 넣어 가장 작은 수를 만드는 문제다.

 괄호를 적절히 넣는다는 말은 그냥 계산 우선순위를 만들라는 것이고 가장 작은 수를 만들기 위해서는 숫자와 -사이에 괄호가 있다면 수가 -가 되어서 가장 작은 수가 될 것이다.

이 예제를 보면 결국

$$ 55-(50+40) $$

이러한 식이 되어 결과값이 35가 나오게 된다.

 이는 이후 +가 나오면 위 식과 같이 한번에 -를 하게되고 만약 -가 나온다면 한 번 괄호를 닫았다가 다시 괄호를 열게된다. 즉, 이후 어떠한 연산자가 나오든지 상관없이 쭉 -연산만 진행해주면 된다. 따라서 minus에 관한 bool타입 변수를 만들어서 이를 확인하면 될 것 같다.

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


int main() {
    int res = 0;
    string str, num;
    bool minus = false;
    cin >> str;


    for(int i = 0; i <= str.length(); i++) {
        if(str[i] == '-' || str[i] == '+' || i == str.length()) {
            if(minus) res -= stoi(num);
            else res += stoi(num);
            num = "";
        } else {
            num += str[i];
        }

        if(str[i] == '-') minus = true;
    }
    cout << res << endl;
    return 0;
}