[백준] 팰린드롬 만들기 (1254번)

문제

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다.

동호는 규완이를 위한 깜짝 선물을 준비했다. 동호는 규완이가 적어놓고 간 문자열 S에 0개 이상의 문자를 문자열 뒤에 추가해서 팰린드롬을 만들려고 한다. 동호는 가능하면 가장 짧은 문자열을 만들려고 한다.

동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 S가 주어진다. S의 길이는 최대 1000이다.

출력

첫째 줄에 동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력한다.

---

문자열의 끝에 문자를 추가해 팰린드롬을 만드는 문제이다.

중간에도 추가가 가능한 줄 알고 뻘짓을 했다.

끝에만 문자를 추가할 수 있기 때문에 aabcaa인 경우에 aabcaacbaa가 답이 된다. 

 

해결방법은 인덱스가 0인 지점부터 차례대로 조사하며 팰린드롬이 되는 최소한의 시작 위치를 찾는 것이다.

aabcaa인 경우에는 맨 뒤의 aa만 팰린드롬이 가능하다 따라서 aa는 그대로 두고 나머지 aabc만 뒤집어서 추가해주면 가장 짧은 팰린드롬 문자열이 생성된다.

aabcba를 생각해보자. 맨 앞의 a를 제외하고 나머지 abcba가 팰린드롬이므로 마지막에 a만 추가해주면 팰린드롬이 성립한다.

 

이에 맞게 구현해주자. 시작 위치부터 차례대로 조사하며 특정 위치부터 마지막까지의 부분 문자열이 팰린드롬이라면, 전체 길이에서 시작 위치에 해당하는 길이만큼 더해서 출력하면 된다. 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%AC%20%EB%A7%8C%EB%93%A4%EA%B8%B0%20(1254%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <memory.h>
using namespace std;
string str;
int n = str.size();

bool isPalin(int idx) {
	int half = (n - idx) / 2;
	for (int i = 0; i < half; i++) {
		if (str[idx + i] != str[n - 1 - i]) return false;
	}
	return true;
}

int main()
{
	cin >> str;
	n = str.size();

	for (int i = 0; i < n; i++) {
		if (isPalin(i)) {
			cout << n + i;
			return 0;
		}
	}
}