[알고리즘] 백준 1254번: 팰린드롬 만들기 (C++), 같은 실수 반복하지 않기

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

1254번: 팰린드롬 만들기

 

DFS로 구현을 하려 했던 문제이다. 26가지 경우의 수(알파벳 개수) 중에 모든 경우를 따져보며 하나씩 더해갈 때마다 지금 문자열이 팰린드롬인가?를 따져보려 했었다. 하지만, 이전에 반복되었던 DFS 관련 실수가 다시 일어났다. 답을 구현하는 종료 조건이 명확하지만 다른 리커시브 콜은 계속 무한 루프를 돌리고 있었던 점을 반복 실수했다.

(DFS로 구현하려 했던 코드는 맨 아래에)

(DFS 무한 루프 첫 실수는 아직 포스팅하지 않음 >> 포스팅 예정)

---

솔루션

그렇다면 어떻게 해야 할까? 어떠한 문자열이 팰린드롬인지 파악하기 위해서는 '스택'이 떠올랐다. 반만큼 넣고(push), 나머지 반은 스택의 top과 같다면 pop, 다르다면 팰린드롬이 아니다를 파악할 수 있겠다는 논리가 떠올랐다. 하지만, 어떤 문자열을 추가하고, 그 길이를 구하는 것이 문제에서 요구되는 내용이라 솔루션을 내기 어려웠다.

 

[스택을 활용하여 팰린드롬인지 판단하는 함수]

bool isRight(string temp) {
	if (temp.size() == 1) {
		return 1;
	}

	stack<char> s;
	if (temp.size() % 2 == 0) {
		for (int i = 0; i < (temp.size() / 2); i++) {
			s.push(temp[i]);
		}
		for (int i = temp.size() / 2; i < temp.size(); i++) {
			if (s.top() == temp[i]) {
				s.pop();
			}
			else {
				return 0;
			}
		}
		return 1;
	}
	else {
		for (int i = 0; i < (temp.size() / 2); i++) {
			s.push(temp[i]);
		}
		for (int i = (temp.size() / 2) + 1; i < temp.size(); i++) {
			if (s.top() == temp[i]) {
				s.pop();
			}
			else {
				return 0;
			}
		}
		return 1;
	}
}

 

참고했던 솔루션에서는 참신한 솔루션을 제안했다.

(+참고 https://jungahshin.tistory.com/96)

 

예를 들어, "aabcda"라는 문자열이 있으면 첫 번째 a를 제외한 부분 문자열은 "abcda"로 팰린드롬이다. 즉, 뒤에 a를 하나 더 추가하면 팰린드롬이 된다는 솔루션이다.

 

>> n번째부터 부분 문자열을 구한다. n번째에서 팰린드롬을 만족하는 부분 문자열이 있다면 1 ~ n - 1 만큼의 문자열을 뒤에 더해주면 모든 문자열이 팰린드롬이 된다.

---

부분 문자열 구하는 함수 substr

그렇다면 부분 문자열은 어떻게 구할까? 직접 구현할 수 있지만 부분 문자열을 구하는 함수가 있다.

substr(부분 문자열의 시작 인덱스, 부분 문자열의 사이즈)

https://modoocode.com/235

C++ 레퍼런스 - string 의 substr 함수

---

소스 코드

#include <iostream>
#include <stack>
using namespace std;

string value;

bool isRight(string temp) {
	if (temp.size() == 1) {
		return 1;
	}

	stack<char> s;
	if (temp.size() % 2 == 0) {
		for (int i = 0; i < (temp.size() / 2); i++) {
			s.push(temp[i]);
		}
		for (int i = temp.size() / 2; i < temp.size(); i++) {
			if (s.top() == temp[i]) {
				s.pop();
			}
			else {
				return 0;
			}
		}
		return 1;
	}
	else {
		for (int i = 0; i < (temp.size() / 2); i++) {
			s.push(temp[i]);
		}
		for (int i = (temp.size() / 2) + 1; i < temp.size(); i++) {
			if (s.top() == temp[i]) {
				s.pop();
			}
			else {
				return 0;
			}
		}
		return 1;
	}
}

int main() {
	cin >> value;

	int answer = value.size();
	for (int i = 0; i < value.size(); i++) {
		string temp = value.substr(i, value.size() - i);
		//cout << temp << '\n';
		if (isRight(temp)) { // 팰린드롬이 맞나?
			answer += value.size() - temp.size();
			break;
		}
	}

	cout << answer;
}

---

DFS로 구현했던 문제

종료 조건을 해결했더라도 시간 초과가 일어났을 거 같다. 최악의 경우에는 26^50 시간 복잡도 가질 것으로 보이기 때문에..

// 똑같은 실수 >> dfs의 종료 조건이 없어서 나머지 재귀 조건들은 탈출 못 함
// 종료 조건 만들어줌 >> string 입력값의 사이즈 두 배 이상 리커시브 하는 건 답이 없다는 뜻
// 으로 간주하고 종료조건을 만듬
#include <iostream>
#include <vector>
using namespace std;

char alpha[27];
string idx;

bool evenCheck(string value) {
	int size = value.size();
	int right = (size / 2);
	int left = (size / 2) - 1;

	for (int i = right; i < value.size(); i++) {
		if (value[left] != value[i]) {
			return 0;
		}
		left--;
	}

	return 1;
}

bool oddCheck(string value) {
	int size = value.size();
	int right = (size / 2) + 1;
	int left = (size / 2) - 1;

	for (int i = right; i < value.size(); i++) {
		if (value[left] != value[i]) {
			return 0;
		}
		left--;
	}

	return 1;
}

void dfs(string value, int stringSize) {
	if (value.size() >= stringSize * 2) {
		return;
	}

	bool flag = 0;
	if (value.size() % 2 == 0) {
		if (evenCheck(value)) {
			flag = 1;
		}
	}
	else {
		if (oddCheck(value)) {
			flag = 1;
		}
	}

	if (flag == 1) {
		cout << value.size();
		return;
	}

	for (int i = 1; i <= 26; i++) {
		dfs(value + alpha[i], stringSize);
	}
}

int main() {
	string idx;
	cin >> idx;

	for (int i = 1; i <= 26; i++) {
		alpha[i] = 'a' + (i - 1);
	}

	dfs(idx, idx.size());
	return 0;
}

---

느낀 점

논리가 엄청 신선하게 다가왔다. 문자열 자체도 하나의 알고리즘 키워드로 느끼게 해주었다.

업 솔빙 필요한 문제!