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에 포함되어있는 여러 함수들을 사용할 수 있게된다.
이는 잘 사용한다면 큰 도움이 될 것 같다.
'PS' 카테고리의 다른 글
| [BOJ] 1094 막대기 (0) | 2023.02.12 |
|---|---|
| [BOJ] 1013 Contact (0) | 2023.02.09 |
| [BOJ] 1541 잃어버린 괄호 (0) | 2023.01.29 |
| [BOJ] 4949 균형잡힌 세상 (0) | 2023.01.17 |
| [BOJ] 1920 수 찾기 (0) | 2023.01.16 |
