백준 17609 c++ "회문" -PlusUltraCode-

https://www.acmicpc.net/problem/17609

 

 

[필자 사고]

하나하나 브루스알고리즘을 이용하면 시간초과가 난다.

팰린드롬 알고리즘 하면 투포인터가 생각이 났다.

그러나 이 문제에서 하나의 문자열을 삭제할시 조건도 있어서 어떻게 이 난관을 돌파할 지가 고민이였다.

생각해보니 처음 idx 와 끝idx를 비교해 가면서 만약 서로 다른 글자가 만날시 처음 idx +1 혹은 endIdx -1 둘중 하나의 인덱스를 옮긴 뒤 회문 함수를 실행시켜서 성공하면 회문 아니면 종료 형태로 문제를 해결했다.

 

아래는 자세한 코드해설이다.

[코드 해설]

입력받은 문자열이 완벽한 회문인지(앞뒤로 읽었을 때 같은지), 아니면 한 글자만 삭제하면 회문이 되는지 판단하는 코드입니다.

먼저 입력받은 문자열을 양 끝에서부터 가운데로 좁혀가며 문자를 하나씩 비교합니다.

• 두 문자가 같으면 양 끝 인덱스를 한 칸씩 좁혀 다음 문자를 비교합니다.
• 두 문자가 다르면, 두 가지 경우를 체크합니다:
  1. 왼쪽 문자를 하나 제외하고 나머지 문자열이 회문인지 검사.
  2. 오른쪽 문자를 하나 제외하고 나머지 문자열이 회문인지 검사.
• 두 경우 중 하나라도 회문이면 "유사회문(결과값 1)"이고, 둘 다 아니면 "회문이 아님(결과값 2)"입니다.

비교 과정에서 모든 문자가 같으면 "완벽한 회문(결과값 0)"으로 판단됩니다.

[소스 코드]

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

string str;
int T;

bool checkPalindrome(int start, int end) {
	while (start < end) {
		if (str[start] == str[end]) {
			start++;
			end--;
		}
		else return false;
	}

	return true;
}

int Game_Start() {
	int startIdx = 0;
	int endIdx = str.size() - 1;

	while (startIdx < endIdx) {
		if (str[startIdx] != str[endIdx]) {
			if (checkPalindrome(startIdx + 1, endIdx) || checkPalindrome(startIdx, endIdx - 1)) {
				return 1;
			}
			else {
				return 2;
			}
		}
		startIdx++;
		endIdx--;
	}
	return 0;
}

int main(void) {
	cin >> T;
	while (T--) {
		cin >> str;
		cout << Game_Start() << '\n';
	}
}