https://www.acmicpc.net/problem/17609
#include <iostream>
using namespace std;
string str;
int check(int l, int r, bool palin) {
while (l < r) {
if (str[l] != str[r]) {
if (palin) {
if (check(l + 1, r, false) == 0 || check(l, r - 1, false) == 0) return 1;
}
return 2;
}
l++; r--;
}
return 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
for (int test = 0; test < t; test++) {
cin >> str;
cout << check(0, str.size() - 1, true) << "\n";
}
return 0;
}
투 포인터 문제이다. 입력을 받고, 회문, 유사회문, 나머지를 판별하는 코드를 작성하는 문제이다.
풀이
int check(int l, int r, bool palin) {
while (l < r) {
if (str[l] != str[r]) {
if (palin) {
if (check(l + 1, r, false) == 0 || check(l, r - 1, false) == 0) return 1;
}
return 2;
}
l++; r--;
}
return 0;
}
우선 문자열의 맨 앞과 맨 뒤부터 가운데로 포인터를 옮기면서 문자를 하나씩 비교해 간다. palin에는 팰린드롬 여부가 들어간다. 문자를 비교하다 다른 문자가 온다면 두 가지로 나누어질 수 있다.
1. 왼쪽의 문자를 제거하면 회문이 되는 경우
2. 오른쪽의 문자를 제거하면 회문이 되는 경우
둘 중 하나의 조건을 충족할 경우 유사회문이므로 1을 출력한다. 그러나 팰린드롬이 아님이 확정이 난 후에 또 왼쪽과 오른쪽의 문자가 다를 경우 2를 출력한다. 문제가 없다면 회문이므로 0을 출력한다.
'Coding Test' 카테고리의 다른 글
백준 17073 나무 위의 빗물 (1) | 2024.05.21 |
---|---|
백준 1766 문제집 (0) | 2024.05.20 |
백준 2224 명제 증명 (0) | 2024.05.18 |
백준 2015 수들의 합 4 (0) | 2024.05.18 |
백준 14621 나만 안되는 연애 (0) | 2024.04.13 |