[BOJ][백준]그리디 알고리즘-17609번 회문

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

17609번: 회문

문제

회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다.

여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력해야 한다.

입력

입력의 첫 줄에는 주어지는 문자열의 개수를 나타내는 정수 T(1 ≤ T ≤ 30)가 주어진다. 다음 줄부터 T개의 줄에 걸쳐 한 줄에 하나의 문자열이 입력으로 주어진다. 주어지는 문자열의 길이는 3 이상 100,000 이하이고, 영문 알파벳 소문자로만 이루어져 있다.

출력

각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다.

 

---

 

 

풀이법 접근이 간단하다고 생각해서 딱히 포스팅을 적으려고 한건 아닌데 내 풀이에 꿀을 발라놨는지 많은 분들이 코드를 뜯어보셨다.  수행 시간이 12ms로 눈에 띄게 적은 것도 아닌데 15분이나 풀이를 뜯어보셨다.

풀이는 전체적으로 그리디이긴한데, 차라리 굳이 구분을 하자면 그리디보다는 완탐에 가깝다고 생각한다.

우선 회문 판단하는 건 is_palindrome 함수로 간단하게 걸러주고, 유사회문인지 어떻게 판단을 할지가 이 문제의 주요 골자인데,  left와 right를 하나씩 중앙으로 전진시키다가 left에 있는 글자와 right에 있는 글자가 다르다면 left를 skip하든, right를 skip 해서 left와 right가 중앙에서 만나는 것까지 성공한다면 유사회문이 된다. 문제 해결 방식이 dp 스럽지만 메모이제이션은 필요 없을뿐더러 N제한이 10만이라 할 수도 없다. skip횟수가 1번으로 정해져 있어 부분 문제가 많이 나뉘지 않아 O(N) 정도로 충분히 시간제한을 통과한다.

 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int t,N;
string s;

bool is_palindrome()
{
    int left=0,right=N-1;
    while(left<=right)
    {
        if(s[left++]!=s[right--])return false;
    }
    return true;
}

bool can_palindrome(int left,int right,bool can_skip)
{
    if(left>right)return true;
    if(s[left]==s[right])return can_palindrome(left+1,right-1,can_skip);
    else if(can_skip) return max(can_palindrome(left+1,right,false),can_palindrome(left,right-1,false));
    else return false;
}

int getAns()
{
    if(is_palindrome())return 0;
    else if(can_palindrome(0,N-1,1)) return 1;
    else return 2;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>t;
    while(t--)
    {
        cin>>s;
        N=s.size();
        cout<<getAns()<<"\n";
    }

}