백준 17609_회문

[youbeen2798]

문제 링크 : https://www.acmicpc.net/problem/17609
난이도 : 골드 5

문제

• 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열은 "회문"
  ex) abba, comwwmoc, kayak
• 한 문자를 삭제하여 회문이 된다면 “유사회문”
  ex) summuus, xabba
• 회문이나 유사회문도 아닌 일반 문자열
  ex) xabbay, comcom

입력으로 받은 문자열이 회문이라면 2를, 유사회문이라면 1을, 일반 문자열이라면 0을 출력한다.

접근방법1

• 문자열을 처음과 끝을 비교하여 둘이 같다면, 앞뒤를 삭제한다.
• 만약, 처음과 끝이 다르다면, 처음을 삭제해보고 회문이 아니라면, 다시 끝을 삭제하여 회문 여부를 확인하였다.
• 이중 for문이 들어가기 때문에, 시간초과

접근방법2(현재답안)

• palindrome함수에 회문과 유사회문을 구분할 수 있는 check인자를 넣어준다.
• 따라서, 일반 회문일 때, (check이 0) left와 right 값이 다르다면 left를 지운 문자열과 right를 지운 문자열 중 회문이 있다면, 1을 출력
• 만약, left를 지운 문자열과 right를 지운 문자열 모두 회문이 아니라면 2 출력
• 만약, check가 1일때, left와 right 값이 다르다면, 2 출력

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int T;

int palindrome(string s, int check) {
	int left = 0;
	int right = s.size() - 1;

	while (left < right) {
		if (s[left] != s[right]) { //만약 앞뒤가 다를 때
			int len = right - left;
			if (check == 0) {
				if (palindrome(s.substr(left, len), 1) == 0 || palindrome(s.substr(left + 1, len), 1) == 0) { //앞 또는 뒤를 자른 문자열이 회문일때
					return 1;
				}
				else {
					return 2;
				}
			}
			else { //유사회문일 때, 다시 한번 앞뒤가 다르다면
				return 2;
			}
		}
		else {
			left++;
			right--;
		}
	}

	return 0;
}
int main() {
	cin >> T;

	for (int test_case = 0; test_case < T; test_case++) {
		string st;
		cin >> st;

		cout << palindrome(st, 0) << "\n";
	}
}

[ghdcksgml1]

올 좀 치네

[youbeen2798]

훗!