백준 1254 c++ "팰린드롬 만들기" -PlusUltraCode-

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

 

[필자 사고]

끝에서 부터 최대가 되는 팰린드롬 글자를 찾아야 된다.

찾은 뒤에 기본 문자열 크기 와 찾은 팰린드롬 글자 수를 더하면 답을 찾을 수 있다.

 

그럼 생각해보자 왜 이러한 방식으로 문제를 해결할 수 있었는지 

문자열을 똑같이 뒤집는다고 가정할때 이미 기존 문자열에 팰린드롬이 존재하면 해당 부분을 제외한

나머지 부분만 뒤집으면 팰린드롬 완성이다.

[코드 해설]

2 . 입력 처리 (Input 함수)

Input() 함수는 표준 입력으로부터 하나의 문자열을 입력받아 전역 변수 word에 저장한다. 이 문자열은 이후 회문 검사를 위한 대상이 된다.

---

3. 회문 검사 함수 (checkFelindrom 함수)

checkFelindrom(int startIdx, int endIdx) 함수는 word 문자열의 부분 문자열이 회문인지 여부를 판단한다.
검사 방식은 양쪽 끝에서 시작하여 가운데로 이동하면서, 문자가 서로 같은지 비교한다.

• 만약 startIdx부터 endIdx까지의 부분 문자열이 모두 대칭이면 true를 반환한다.
• 그렇지 않으면 false를 반환한다.

이 함수는 회문 여부를 판별하기 위한 핵심 도구이다.

---

4. 게임 시작 및 결과 출력 (Game_Start 함수)

Game_Start() 함수는 문자열을 가능한 가장 짧게 회문으로 만들기 위해, 문자열 뒤에 최소한의 문자만을 덧붙이는 방법을 찾는다.

작동 방식은 다음과 같다:

1. 문자열의 각 인덱스 i에 대해 i부터 끝까지의 부분 문자열이 회문인지 검사한다.
2. 그 부분이 회문이라면, 이 부분 앞에 있는 접두사를 뒤집어서 붙이면 전체 문자열이 회문이 된다.
3. 이때 덧붙여야 할 문자의 개수는 i개의 접두사이므로, 최종 회문 문자열의 길이는 word.size() + i가 된다.
4. 가장 앞에서부터 회문이 되는 구간을 찾으면, 바로 결과를 출력하고 종료한다.

---

5. 메인 함수 (main)

main() 함수는 Input()과 Game_Start() 함수를 차례대로 호출하여 전체 프로그램의 흐름을 실행한다.

[소스 코드]

#include <iostream>
#include <cstring>
#include <string>
#include <vector>

using namespace std;

string word;

bool checkFelindrom(int startIdx, int endIdx) {

	while (startIdx <= endIdx) {
		if (word[startIdx] != word[endIdx]) {
			return false;
		}
		startIdx++;
		endIdx--;
	}
	return true;
}

void Input() {
	cin >> word;
}

void Game_Start() {
	int resultStartIdx = -1;
	for (int i = 0; i < word.size(); i++) {
		if (checkFelindrom(i, word.size() - 1)==true) {
			resultStartIdx = i;
			break;
		}
	}

	cout << word.size() + resultStartIdx;
}

int main(void) {
	Input();
	Game_Start();
}