문제
풀이
두 포인터, 문자열 문제이다.
- 두포인터와 재귀 함수로 해당 문자열이 팰린드롬인지 판별한다.
- 현재 start와 end에서의 문자가 맞지 않다면 start + 1과 end까지와 start부터 end - 1까지 문자열을 확인하도록 함수를 재귀한다.
- 이미 문자가 맞지 않은 상태에서, 다시 start와 end의 문자가 맞지 않다면 회문이나 유사회문이 아니다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 투 포인터로 양 옆에서 접근하며 팰린드롬을 체크한다.
int solution(string current, int start, int end, int in_diff_count)
{
int diff_count = in_diff_count;
while (start <= end)
{
if (current[start] == current[end])
{
start++;
end--;
continue;
}
// current[start]와 current[end]가 서로 맞지 않다면
if (current[start] != current[end])
{
// diff_count를 1 증가시킨다.
diff_count++;
// 이미 diff_count가 1인 상태에서 함수가 실행되었다면
// 재귀를 하지 않고 즉시 diff_count를 반환한다.
if (diff_count > 1)
{
break;
}
// start와 end 둘 중 하나를 삭제한 상태에서 다시 투 포인터를 실시하도록 재귀한다.
diff_count = min(solution(current, start + 1, end, diff_count),
solution(current, start, end - 1, diff_count));
break;
}
}
return diff_count;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
while (T--)
{
string current;
cin >> current;
int start = 0;
int end = current.length() - 1;
int diff_count = solution(current, start, end, 0);
cout << diff_count << '\n';
}
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준][C++] 30508: 고인물이싫어 (0) | 2023.11.17 |
---|---|
[백준][C++] 17822: 원판 돌리기 (0) | 2023.11.16 |
[백준][C++] 9527: 1의 개수 세기 (0) | 2023.11.14 |
[백준][C++] 2170: 선 긋기 (0) | 2023.11.13 |
[백준][C++] 17135: 캐슬 디펜스 (1) | 2023.11.12 |