[BOJ] 10988 팰린드롬인지 확인하기

www.acmicpc.net/problem/10988

10988번: 팰린드롬인지 확인하기

나는 팰린드롬을 매우 좋아한다

팰린드롬 그 자체도 좋고 관련 문제도 좋고

 

팰린드롬을 확인하는 코드는 다양한 방법으로 구현할 수 있지만

이번 주 초급 스터디에서 Divide & Conquer를 강의했는데

이 문제를 Divide & Conquer의 관점에서 바라볼 수 있을거 같아서 준비했다.

 

설명은 그림 위주라 생략하고 코드만 넣어야겠다

bool Palin(int left, int right, string& s);

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	string s; cin >> s;

	cout << Palin(0, s.length() - 1, s);	// 가장 처음 확인하는 left, right는 문자열의 양 끝

	return 0;
}

bool Palin(int left, int right, string& s) {
	if (!(left <= right)) {			// 더 이상 확인할 문자열이 남아있지 않다
		return true;				// 지금까지 모든 검사를 통과했으므로 true 반환
	}

	if (s[left] != s[right]) {		// 현재 확인중인 문자열의 양 끝 문자가 다르면 Palindrome 아님
		return false;				// false 반환
	}
	else {
		return Palin(left + 1, right - 1, s);	// 양 끝 문자를 제외한 문자열을 다시 확인
	}
}