백준 15927번 회문은 회문아니야!!

문제 링크입니다: https://www.acmicpc.net/problem/15927

비교적 쉬운 문제였지만 어렵게 생각했기 때문에 많이 틀린 문제였습니다.

결국 같은 학교 학우인 ssangba55님(blog.naver.com/pasdfq)과 sansan709(degurii.tistory.com)님의 도움 덕분에 풀 수 있었습니다.

개인적으로 이 문제는 그리디(Greedy) 알고리즘으로 분류되어야한다고 생각합니다.

알고리즘은 아래와 같습니다.

1. 문자열의 양 끝부터 순차적으로 회문 조건을 만족하는지 판별합니다.

i) 회문 조건을 만족하지 않는다면 문자열이 팰린드롬(palindrome) 즉, 회문이 아니기 때문에 답은 문자열의 전체 길이입니다.

ii) 문자열이 회문이라면 앞에 있는 문자나 뒤에 있는 문자를 제외시키면 회문이 아니기 때문에 답은 (문자열의 전체 길이 - 1)입니다.

2. 1번의 ii)번이 항상 만족하는 것은 아닙니다. 모든 문자가 똑같을 경우 문자열에서 몇 개의 문자를 빼든 회문이기 때문에 -1을 출력해줘야합니다.

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

 

int main(void)

{

        string s;

        cin >> s;

 

        bool palindrome = false;

        bool answer = false;

 

        for (int i = 0; i < s.length() / 2; i++)

        {

                 //회문이 아니라면

                 if (s[i] != s[s.length() - 1 - i])

                 {

                         answer = true;

                         break;

                 }

                 //전부 다 같은 문자가 아니라면

                 else if (s[i] != s[i + 1])

                         palindrome = true;

        }

       

        if (answer)

                 cout << s.length() << "\n";

        else

        {

                 //전부 같은 문자가 아닐 경우

                 if (palindrome)

                         cout << s.length() - 1 << "\n";

                 //전부 같은 문자

                 else

                         cout << -1 << "\n";

        }

        return 0;

}

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~