[C++] 백준 1254 - 팰린드롬 만들기

문제 - 팰린드롬 만들기 (Silver 2)

[백준 1254] https://www.acmicpc.net/problem/1254

풀이 전략

• 팰린드롬인지 확인하는 코드는 여러번 해왔기 때문에 문제가 없다. 하지만, 예제 4번처럼 중간의 부분 문자열이 팰린드롬인 경우는 따로 확인을 해줘야 한다.
• 브루트포스 알고리즘을 사용해 문자열 전체를 탐색한다.
• 예제 1,2,3,4 모두 다른 case이기 때문에 조건을 나열해야 한다.

참고

Palindrome

나무위키 - 회문

이전에 Tenet과 우영우를 예시로 들어서 설명 했었지만, 또 설명을 하면 데칼코마니처럼 앞뒤가 똑같은 숫자, 문자이다. 그렇기 때문에 팰린드롬 여부를 확인할 때는 포인터가 1개 혹은 2개가 필요하다.

• 1개가 필요한 경우는 포인터가 처음(0)과 (문자열(숫자)의 길이-포인터-1)로 나눠서 같은지를 확인하는 방법이고
• 2개가 필요한 경우는 2중 for문으로 확인하면 된다.

[팰린드롬 코드]
One pointer

bool isPalin=true;
string str;
int len=str.length();

for(int i=0;i<len/2;i++){
	if(str[i]!=str[len-i-1]){
    	isPalin=false;
    }
}

Two pointer

bool isPalin=true;
string str;
int len=str.length();

for(int i=0;i<len;i++){
	for(int j=len-1;j>=i;j--){
    	if(str[i]!=str[j]){
        	isPalin=false;
        }
    }
}

브루트포스 알고리즘

: 앞에서부터 끝까지 차근차근 탐색하는 알고리즘으로 무식한 방법이지만 확실한 방법이기도 하다.
시간 복잡도 : O(NxM) [Text길이 * Pattern 길이]

[브루트포스 코드]

int BruteForce(string text,string pattern){
	for (int i=0;i<=text.size()-pattern.size();i++){
		int j=0;
		while(j<pattern.size()&&text[i+j]==pattern[j]{
			j++;
		}
		if (j==pattern.size())
			return i;
	}
	return -1;
}

소스 코드

#include <iostream>
using namespace std;

bool isPalin(string str){
    int start=0,end=str.length()-1;
    while(start<end){
        if(str[start]!=str[end]){
            return false;
        }
        start++;
        end--;
    }
    return true;
} // 중간의 코드와 중복되지만, 예제 4번을 위해 선언

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

    string str;
    cin>>str;

	int length=str.length();
    
    int count=0;
    for(int i=0;i<len/2;i++){
        if(str[i]==str[len-i-1]){
            count=len;
        }//str 자체가 팰린드롬이면 문자열 길이가 곧 count
        else if(str[i]==str[len/2+i]){
            count=len+1;
        }/* abab처럼 똑같은 문자열이 반복되면 
        	제일 뒤에 a만 추가하면 되기 때문에 문자열 길이+1*/
    }
    for(int i=0;i<len;i++){
        string tmp=str.substr(i,len-i); // 부분 문자열을 tmp에 복사
        if(isPalin(tmp)){
            count=len+i;
            break;
        } /* tmp가 팰린드롬이면 문자열 길이에 
        	팰린드롬이 되는 부분 문자열의 길이를 더해줌*/
    }
    cout<<count<<'\n';
    return 0;
}

결과