https://www.acmicpc.net/problem/25501
문제
> 정휘는 후배들이 재귀 함수를 잘 다루는 재귀의 귀재인지 알아보기 위해 재귀 함수와 관련된 문제를 출제하기로 했다.
> 팰린드롬이란, 앞에서부터 읽었을 때와 뒤에서부터 읽었을 때가 같은 문자열을 말한다.
팰린드롬의 예시로 AAA, ABBA, ABABA 등이 있고, 팰린드롬이 아닌 문자열의 예시로 ABCA, PALINDROME 등이 있다.
> 어떤 문자열이 팰린드롬인지 판별하는 문제는 재귀 함수를 이용해 쉽게 해결할 수 있다.
> 아래 코드의 isPalindrome 함수는 주어진 문자열이 팰린드롬이면 1, 팰린드롬이 아니면 0을 반환하는 함수다.
> 정휘는 아래에 작성된 isPalindrome 함수를 이용하여 어떤 문자열이 팰린드롬인지 여부를 판단하려고 한다.
> 구체적으로는, 문자열 S를 isPalindrome 함수의 인자로 전달하여 팰린드롬 여부를 반환값으로 알아낼 것이다.
> 더불어 판별하는 과정에서 recursion 함수를 몇 번 호출하는지 셀 것이다.
> 정휘를 따라 여러분도 함수의 반환값과 recursion 함수의 호출 횟수를 구해보자.
접근
먼저 재귀부분인 recursion함수부터 구현을 한다.
1. 호출횟수의 누적
일단 문제에서 재귀가 호출된 횟수를 누적시켜야한다고 했으므로 recursion함수가 실행되자마자 cnt를 누적시켜야한다.
2. 재귀의 종료
그다음은 재귀의 탈출이다. 여기선 팰린드롬을 만족할때 1을 반환하고 아니면 0을 반환하라고 했으므로 이를 탈출 조건으로 정의해준다.
3. 재귀
위의 탈출조건에 부합하지 않아 다시 재귀를 해야하므로 조건을 변화시켜 재귀에 다시 넣어야한다.
그래서 이 문제에선 문자열의 인덱스를 변화시켜야해서 인덱스의 값에 변화를 주어 재귀한다.
4. isPalindrome함수
isPalindrome함수에선 재귀함수 recursion을 호출하며 동시에 초기값을 주는 역할을 한다. 문자열을 입력받았을 때 이 문자열, 첫 인덱스 0, 문자열 길이 -1 을 한 끝인덱스를 넣어줘야한다.
5. main문
main문에선 재귀함수의 호출과 출력만 해주면 된다. 재귀함수에서 세부동작은 다 해주기 때문이다.
문제해결
> 1번 과정을 구현하기 위해 recursion함수가 호출되면 일단 탈출시도, 검증 전 cnt의 값을 누적시켜준다. 탈출을 하기 위해서든지, 다시 재귀를 들어가기 위해서든지 일단 recursion함수가 호출되기 때문에 제일먼저 해준다.
> 그 다음 탈출부분에대해 1로 탈출할 때의 조건이다. 여기선 인덱스를 순회하며 문자열의 문자를 비교하기 때문에 시작인덱스부터의 증가값 L과 끝인덱스부터의 감소값 R을 비교해
L이 R과 같거나 크다 즉, 비교가 지속되어 문자열의 수가 홀수 일땐 중간문자에 도달하거나 문자열이 짝수여서 인덱스가 교차될때를 따져준다.
0일 땐 문자가 다를때 이므로 받은 문자열 s에 대해 s[l]과 s[r]이 다르다면 0을 반환한다.
> 위에서 인덱스 r이 l보다 크고, 각 인덱스의 문자가 서로 같다라는게 검증이 되면 이제 다음 문자를 비교해야 하므로 재귀로 해당 recursion함수에 인덱스의 변화를 입력해줘야한다.
좌측부터 증가하는 l에 +1을 우측부터 감소하는 r에대해 -1을 넣어준다.
그럼 함수가 진행되면 예를들어 처음엔 0, 7 다음엔 1,6 그리고 2, 5이런식으로 재귀가 이루어진다.
> isPalindrome함수는 문자열 입력값 마다 문자열과 인덱스의 끝이 다르기 때문에 이를 고려해 인자로 받은 s값을 넣고, 인덱스는 0부터이므로 s의 길이(크기)-1 을 r로 넣어 recursion함수, 재귀를 시작해준다.
> main문에선 함수의 호출과 출력만 담당해주면 되므로
테스트 케이스의 개수를 받고 테스트 케이스만큼 문자열 입력과, 해당 문자열 검증을 위한 cnt의 값을 출력해주도록 한다.코드
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
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()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
while (T--)
{
cnt = 0;
string str;
cin >> str;
cout << isPalindrome(str)<< " " << cnt << '\n';
}
}
후기
테스트 케이스의 개수가 1000개까지고 문자열의 길이도 1000개 까지이므로 재귀에 넣었을 떄 문자열 s를 그냥 string s를 인자로 해서 받았더니 시간초과가 났다.
이렇게 하면 문자열을 "복사"하기 때문에 재귀에선 엄청난 처리량이 발생한다고 한다. 그래서 const - 읽는용(수정하지않음)으로 s를 &s로 "참조"해와야 한다.
기본적인 부분에서 놓쳤다. 항상 기본을 다지자
