[C++] 팰린드롬 만들기 (1254번)

팰린드롬 만들기 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

9001

3919

3274

45.221%

문제

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

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

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

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 최대 50이다.

출력

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

---

문제풀이

하나하나 절차를 생각해보면서 풀면 쉽게 풀 수 있다.

문자열은 반드시 뒤에 추가되고, 팰린드롬으로 만들어야 한다.

abab를 예제로 들어보자.

처음부터 보면, 양 끝이 a, b로 다르다. 즉 팰린드롬이 성립하지 않는다.

그러므로 맨 뒤에 a를 추가해 주어야 한다.

이제 맨 앞의 a는 대칭이 되었다.

다음으로 b를 보자. 양 끝이 b, b로 같다. 그리고 a는 하나이므로 팰린드롬이 성립한다.

 

이를 절차화 해보면 다음과 같다.

1. 왼쪽부터 문자 하나를 읽는다.

2. 해당 문자부터 시작하여 팰린드롬이 만들어지는지 확인한다.

3. 만들어지지 않는다면 문자열의 길이를 1 증가시킨다.

4. 만들어진다면 지금까지 문자열 길이를 출력한다.

 

즉 입력 문자열을 반복문 돌면서 각각 팰린드롬이 만들어지는지 아닌지만 확인하면 간단하게 구현할 수 있다.

 

#include <iostream>
#include <string>

using namespace std;

// 펠린드롬인지 확인
bool check(string s) {
    int start = 0;
    int end = s.size()-1;

    while(start<end) {
        if(s[start] != s[end]) return false;
        start++;
        end--;
    }

    return true;
}

int main() {
    string s;
    cin >> s;
    int start = 0;
    int end = s.size()-1;

    int answer = s.size();
    for(int i=0; i<s.size(); i++) {
        if(check(s.substr(i))) break;
        answer++;
    }

    cout << answer;
    return 0;
}