[백준] 23304 아카라카 (C++)

23304번: 아카라카

2021.11.05 기준 실버 2 문제이다. 재귀 함수를 연습해보기에 괜찮은 문제라 생각된다.

 

문제는 문자열이 하나 주어지고, 그 문자열이 '아카라카 팰린드롬'인지 확인하는 문제이다.

다음 두 조건을 모두 만족해야 '아카라카 팰린드롬'이다.

---

풀이

재귀함수 rec를 이용하여 문자열이 아카라카 팰린드롬인지 확인하였다.

재귀 함수 rec는 다음과 같다.

bool rec(string x) { // 문자열 x가 아카라카 팰린드롬이면 true를 리턴
	if (x.size() == 1) return true;

	string l, r;
	ll tmp = x.size() / 2;
	for (ll i = 0; i < tmp; i++) {
		l += x[i];
	}
	for (ll i = 0; i < x.size() / 2; i++) {
		if (x.size() % 2 == 1) r += x[i + x.size() / 2 + 1];
		else r += x[i + x.size() / 2];
	}
	if (l != r) return false;
	if (rec(l) && rec(r)) return true;
	else return false;
}

 

조건은 위와 같았다.

함수는 다음과 같은 과정을 통해 '아카라카 팰린드롬'인지 확인한다.

(1) 가운데를 기준으로 문자열을 2개(l과 r)로 나눈다. (문자열의 길이가 홀수이면 가운데 문자열은 제외된다.)

 

(2) 문자열 l과 r이 같다면 조건 1을 만족한다. 이것을 만족하지 못하면 '아카라카 팰린드롬'이 아니기 때문에 false를 반환한다. 문자열 l과 r이 같다면 과정 (3)에서 조건 2를 확인해야한다.

 

(3) 접두사와 접미사가 모두 '아카라카 팰린드롬'인지 확인한다. '아카라카 팰린드롬'인지 확인하는 함수가 rec함수이기 때문에 rec함수를 다시 호출하게 된다.

 

위 과정이 계속 재귀적으로 이루어지면서 '아카라카 팰린드롬'인지 확인한다!

---

몇 가지 예시를 보자.

 

다음 문자열들은 '아카라카 팰린드롬'이다.

'AKARAKA'

'a'

'aba'

'aaabaaa'

 

다음 문자열들은 '아카라카 팰린드롬'이 아니다.

WA를 받았다면 아래 예시에서 잘못된 답을 출력하고 있을 것으로 예상된다.

'abcbaabcba'

'abcdcbaabcdcba'

'abba'

---

코드

#include <bits/stdc++.h>
#define INF 9876543210
#define endl '\n'
using namespace std;
using ll = long long;

string s;

bool rec(string x) { // 문자열 x가 아카라카 팰린드롬이면 true를 리턴
	if (x.size() == 1) return true;

	string l, r;
	ll tmp = x.size() / 2;
	for (ll i = 0; i < tmp; i++) {
		l += x[i];
	}
	for (ll i = 0; i < x.size() / 2; i++) {
		if (x.size() % 2 == 1) r += x[i + x.size() / 2 + 1];
		else r += x[i + x.size() / 2];
	}
	if (l != r) return false;
	if (rec(l) && rec(r)) return true;
	else return false;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> s;
	if (rec(s)) cout << "AKARAKA" << endl;
	else cout << "IPSELENTI" << endl;

	return 0;
}