회문( BOJ 17609 )

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

17609번: 회문

 

문제 파악하기

주어진 문자열이 회문인지, 아니면 유사회문인지, 아니면 일반 문자열인지 확인하는 문제입니다. 해당 문자가 회문인 판단은 반복문으로 간단하게 할 수 있지만, 유사회문인지 확인하기 위해서는 별도의 알고리즘이 필요합니다. 저는 여기서 브루트포스 알고리즘을 활용했습니다.

 

문제 해결하기

우선 유사회문인지 판단하는 가장 간단한 알고리즘은 문자열 속 문자를 하나씩 제거하고 확인하는 방법이 있습니다. 이 방법은 정확하지만 문자열의 길이가 100,000인 문자열에 대해서는 확실히 느린 모습을 보여줍니다. 100,000개의 문자 중 하나씩 제외해서 회문인지 확인한다면 해당 알고리즘은 O(N²)이 되며, 이 알고리즘은 1초 안에 정답을 출력할 수 없습니다. 그렇다면 효율적인 방법으로는 어떤 방법이 있을까요?

 

우리는 회문인지 확인하는 함수를 만든다면 살짝 수정해서 유사회문인지 확인하는 함수를 만들 수 있습니다. 그럼 우선, 회문인지 확인하는 함수부터 만들어봅시다. 회문인지 확인하기 위해서는 기본적으로 2개의 매개변수가 필요합니다. 각각 left와 right라고 할 때, 만약 현재 문자열이 회문이라면 left와 right의 문자 값은 항상 같아야 합니다. 만약 한 번이라도 다른 경우가 있다면 회문이라고 할 수 없습니다. 따라서 다음과 같은 함수를 만들 수 있습니다.

void search(int l, int r) {
    // 결과 확인
    if(l>r) ret = 1;
    else {
        if(inp[l] == inp[r]) search(l+1, r-1);
        else return;
    }
}

 

여기에 우리는 한 가지 기능을 첨가해야 합니다. 바로, 유사회문인지 확인하는 기능입니다. 유사회문은 하나의 문자를 제외한 문자열이 회문이라는 뜻입니다. 그 의미는 한 번은 다른 문자가 나와도 된다는 의미라고 볼 수 있습니다. 그렇기에 하나의 매개변수를 추가해봅시다.

void search(int l, int r, int f) {
    if(l>r) {
        // 회문인지 유사회문인지 확인
        if(!f) ret[0] = 1;
        else ret[1] = 1;
 
        return;
    }
    else {
        if(inp[l] == inp[r]) search(l+1, r-1, f);
        else {
            // 회문이 아닌 경우
            if(f) {
                ret[2] = 1;
                return;
            }
 
            // 유사회문인지 확인
            else {
                search(l+1, r, 1);
                search(l, r-1, 1);
            } 
        }
    }
}

 

위의 함수에서 f라는 변수는 지금까지 틀린 적이 있는지 기록하는 변수입니다. 만약 f가 1이라면 지금까지 탐색을 진행하면서 다른 문자열이 1번 나왔다는 의미입니다. f에 따라서 탐색을 더 할 수 있을지 없을지 판단할 수 있으며, 탐색이 성공적으로 끝난 후에는 현재 문자열이 회문인지 유사회문인지 확인할 수 있습니다.

 

소스 코드

#include <iostream>
#include <string>
#include <vector>
#define NMAX 100010
using namespace std;
 
int T;
string inp;
 
int l, r;
int ret[3];
vector< int > ans;
 
void search(int l, int r, int f) {
    if(l>r) {
        // 회문인지 유사회문인지 확인
        if(!f) ret[0] = 1;
        else ret[1] = 1;
 
        return;
    }
    else {
        if(inp[l] == inp[r]) search(l+1, r-1, f);
        else {
            // 회문이 아닌 경우
            if(f) {
                ret[2] = 1;
                return;
            }
 
            // 유사회문인지 확인
            else {
                search(l+1, r, 1);
                search(l, r-1, 1);
            } 
        }
    }
}
 
int main() {
    // init
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    // input
    cin >> T;
    while(T--) {
        cin >> inp;
        l = 0; r = inp.size()-1;
 
        // 회문 검사
        ret[0] = ret[1] = ret[2] = 0;
        search(l, r, 0);
 
        // 결과 확인(0-회문 / 1-유사회문 / 2-회문X)
        for(int k=0;k<3;k++) {
            if(ret[k]) {
                ans.push_back(k);
                break;
            }
        }
    }
 
    // 출력
    for(int val:ans) printf("%d\n", val);
}

후기

문제 상황을 추상화할 수 있는지 확인하는 문제라고 생각합니다. 기본적인 추상화 과정을 거칠 수 있다면 손쉽게 해결할 수 있다고 생각합니다.