공통 부분 수열 확장( BOJ 21762 )

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

21762번: 공통 부분 수열 확장

 

문제 파악하기

주어진 문자열 X와 Y의 공통 부분 수열을 확장할 수 있는지 확인하는 문제입니다. W는 X와 Y의 공통 부분 문자열이며 W를 확장시킬 수 있다면 1을, 확장시킬 수 없으면 0을 출력하는 결정 문제입니다. 단순 반복문을 사용하는 알고리즘을 사용하면 정답을 구할 수 있지만, 1초 안에 해결할 수는 없습니다. 그렇기 때문에 문제를 해결하기 위해서는 효율적인 알고리즘이 필요하며, 이 때에는 슬라이딩 윈도우 기법을 사용할 수 있습니다.

 

문제 해결하기

우선, 문제를 풀기 위해 유념할 점은 X와 Y에서 W가 여러 개 나올 수 있다는 점입니다. 최대 공통 문자열이 아닌, 단순히 공통 문자열이기 때문에 여러 위치에서 W가 있을 수 있으며, 효율적인 탐색을 위해서는 W에 포함된 각각의 문자가 나오는 위치를 알고 있어야 합니다. 그리고 우리는 문자열 X와 Y에서 W의 각각의 문자가 나오는 범위 내에 동일한 문자가 있는지 확인하면 문제를 해결할 수 있습니다. 예를 들어 다음과 같이 입력 예시가 주어졌다고 가정해보겠습니다.

 

X: abacbaca / Y: cbaffbatba / W: baa

 

W의 첫 번째 문자인 b가 X에서 가장 먼저 등장하는 위치는 X[1] 입니다. 그리고 W의 두 번째 문자인 a가 등장하는 가장 마지막 위치는 X[5]입니다. X[7]에도 a가 있지만, 해당 a를 포함해서는 baa를 만들 수 없기 때문에 후보에서 제외합니다. 이렇게 우리는 W의 부분 수열인 [ ba ] 사이에 들어올 수 있는 또 다른 문자가 있는지 보기 위해서는 X[2:4] 구간을 확인하면 됩니다. 마찬가지로 Y에서 b가 가장 먼저 등장하는 위치는 Y[1]이며, 그 다음 문자인 a가 등장하는 가장 마지막 위치는 Y[6]입니다. 따라서, Y[2:5] 구간의 알파벳을 확인하면 됩니다. 결국 우리는 X[2:4]와 Y[2:5] 사이의 문자들 중 공통된 문자가 있는지 확인하면 됩니다. 만약, 같은 문자가 없다면 이번에는 W의 다음 부분 수열인 [ aa ]의 범위를 살펴보고, 공통 부분 수열을 확장할 수 있는지 검사하면 됩니다.

 

이렇게 각각의 문자열에서 공통 부분 수열이 될 수 있는 범위를 중첩 반복문으로 간단하게 확인하면 문제의 정답을 찾을 수 있지만, X와 Y의 길이가 커지면 시간초과에 걸리게 됩니다. 따라서, 공통되는 문자를 기준으로 범위를 슬라이딩 윈도우 기법을 사용해서 중복된 탐색을 제외한다면 문제를 제한 시간 안에 해결할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <utility>
#define AMAX 30
#define PAIR pair<int, int>
using namespace std;
 
int T;
string X, Y, W;
 
int szX, szY, szW;
int idxX, idxY, idxW;
int leftX, rightX, leftY, rightY;
 
int f;
int check[AMAX][2];
PAIR rngX, rngY;
vector< PAIR > WX, WY;
 
vector< int > ans;
 
bool isPossible(int idx) { return check[idx][0]>0 and check[idx][1]>0; }
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    // input
    cin >> T;
    while(T--) {
        // init
        WX.clear();
        WY.clear();
        memset(check, 0, sizeof(check));
 
        // input
        cin >> X >> Y >> W;
        szX = X.length(); szY = Y.length(); szW = W.length();
 
        WX.push_back({-1, 0});
        WY.push_back({-1, 0});
 
        // 공통부분수열이 나올 수 있는 가장 왼쪽 탐색
        idxW = idxX = idxY = 0;
        while(idxW < szW) {
            while(X[idxX]!=W[idxW]) idxX++;
            while(Y[idxY]!=W[idxW]) idxY++;
 
            WX.push_back({idxX++, 0});
            WY.push_back({idxY++, 0});
 
            idxW++;
        }
 
        // 공통부분수열이 나올 수 있는 가장 오른쪽 탐색
        idxW = szW-1; idxX = szX-1; idxY = szY-1;
        while(idxW >= 0) {
            while(idxX>=0 and X[idxX]!=W[idxW]) idxX--;
            while(idxY>=0 and Y[idxY]!=W[idxW]) idxY--;
 
            WX[idxW+1].second = idxX--;
            WY[idxW+1].second = idxY--;
 
            idxW--;
        }
 
        WX.push_back({szX, szX});
        WY.push_back({szY, szY});
 
        // 공통부분수열이 확장가능한지 확인
        idxW = f = 0;
        leftX = rightX = leftY = rightY = 0;
        while(idxW<=szW and !f) {
            // init
            rngX = make_pair(WX[idxW].first+1, WX[idxW+1].second-1);
            rngY = make_pair(WY[idxW].first+1, WY[idxW+1].second-1);
 
            // X/Y 배열 축소
            while(leftX<rngX.first) {
                check[X[leftX]-'a'][0]--;
                if(isPossible(X[leftX]-'a')) f = 1;
 
                leftX++;
            }
            while(leftY<rngY.first) {
                check[Y[leftY]-'a'][1]--;
                if(isPossible(Y[leftY]-'a')) f = 1;
 
                leftY++;
            }
 
            // X/Y 배열 확장
            while(rightX<=rngX.second) {
                check[X[rightX]-'a'][0]++;
                if(isPossible(X[rightX]-'a')) f = 1;
 
                rightX++;
            }
            while(rightY<=rngY.second) {
                check[Y[rightY]-'a'][1]++;
                if(isPossible(Y[rightY]-'a')) f = 1;
 
                rightY++;
            }
 
            idxW++;
        }
 
        ans.push_back(f);
    }
 
    for(int val:ans) printf("%d\n", val);
}
/*
2
ababca
cbabba
baa
aaabbbccc
caacbbc
ccc
ans
1
0
 */

후기

슬라이딩 윈도우 기법을 연습할 수 있는 문제입니다. 문제를 이해하기는 쉽지만 그리디 기법을 사용해서 범위를 탐색하고, 슬라이딩 윈도우 기법을 사용해 시간 복잡도를 줄이는 게 나름 까다롭던 문제입니다. 슬라이딩 윈도우 기법에 조금 익숙해질 필요가 있다는 생각이 들었습니다.