[c++] 백준 1254 팰린드롬 만들기 - 투포인터

[문제]

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

1254번: 팰린드롬 만들기

 

[풀이]

문제를 잘 읽자....문자열 뒤에만 추가할 수 있단다. 그걸 못보고 insert로 중간 삽입해서 풀다가 왜 계속 틀리는 거지??? 멘붕 왔는데...뻘짓했다...

먼저 맨 처음 문자부터 맨 마지막까지 팰린드롬이 되는지를 확인하고 팰린드롬이 되는 첫번째 인덱스를 찾는다. 그럼 전체 문자열 길이+팰린드롬이 되는 첫번째 인덱스 값이 답이 된다.

예를 들어, aabcaa의 경우 마지막 aa만 팰린드롬이 되므로 팰린드롬이 되는 첫번째 인덱스는 4이다. 즉 6+4가 최소 길이이고 aabc aa + cbaa 가 될 것이다. aabcba의 경우 맨 앞에 a를 제외한 abcba가 팰린드롬이다. 따라서 마지막에 a만 추가하면 a abcba + a로 가장 최소길이의 팰린드롬이 된다. 이는 팰린드롬이 되는 첫번째 인덱스가 두번째 a값, 즉 1이므로 6+1인 7이 최소길이이다. 

 

[코드]

 

#include <iostream>
#include <string>

using namespace::std;

string s;

bool isPalindrome(int start, int end, string s){
    while(start<=end){
        if(s[start]==s[end]){
            start += 1;
            end -= 1;
        }
        else{
            return false;
        }
    }
    return true;
}

int main() {
    //만들 수 있는 가장 짧은 팰린드롬의 길이를 출력
    cin >> s;
    //aabc aa + cbaa
    //a abcba + a
    //특정 인덱스부터 문자열의 맨 마지막까지 팰린드롬이 되는 문자열의 시작 위치를 찾음.
    int end = s.length()-1;
    for(int i=0; i<=end; i++){
        if (isPalindrome(i, end, s)){
            cout << s.length()+i;
            return 0;
        }
    }

}