[Greedy] BJ_21762, 공통부분수열확장, 정올

 

 이 문제는 처음 접했을 때, 어떤 알고리즘으로 문제에 접근해야 하는지 생각하기 난해한 문제다. 제목에서 알 수 있듯이 Greedy 문제로, Greedy 문제는 접근법을 떠올리지 못하면 풀이에 쉽게 다가가지 못한다. 이해를 쉽게 하기 위해 아래 예시를 들어 보자. X, Y를 독립적으로 생각하고, 아래와 같이 주어졌다고 한다면 공통 부분 수열인 w를 중심으로 w의 원소인 w[i]의 사이사이에 어떠한 인자들이 들어갈 수 있는지 계산해 보는 것이 필요하다. 즉 w = da인 아래의 케이스 에는 d의 앞에, d와 a의 사이, a의 뒤에 어떤 알파벳이 들어올 수 있는지를 계산하고 X, Y에 각각 동일한 원소가 있다면 확장 가능한 공통부분 수열이라는 것을 확인할 수 있다. 
  w는 이미 공통 부분 수열이기 때문에 위와 같이 구하기 위해서는 w의 각각의 알파벳에 대해서 w가 구성가능한 범위내에서 각각의 알파벳의 최소, 최대 범위를 아는 것이 필요하다. 즉, 가장 처음 등장하는 인덱스와 가장 마지막에 등장하는 인덱스를 정리할 필요가 있다는 뜻이다. 아래의 X 예시에서는 d는 최소 인덱스가 1이고, 최대 인덱스는 6이다. 이를 이용하게 되면 다음과 같이 계산할 수 있기 때문이다. 
 d = [1, 6], a = [2, 7]로 계산되므로, d의 이전에 등장할 수 있는 알파벳의 인덱스는 X의 (-1, 6)의 범위를 살피면 되고, d와 a의 사이는 (1, 7)의 범위를, a 뒤의 인덱스는 (2, 8)이라는 것을 확인할 수 있다. 즉, (이전 알파벳의 최소 인덱스 , 지금 알파벳의 최대 인덱스)의 범위가 되겠다. 맨 처음과 맨 마지막은 -1, 그리고 배열의 크기로 초기화 한다. 이해가 잘 되지 않는다면 아래 설명을 잘 곱씹어 보자.

 

 

 이제 방법론으로 각 알파벳의 최소, 최대 인덱스를 어떻게 구할수 있는지 살펴보자. 단순히 문자열에서 처음 마지막에 등장하는 인덱스를 찾는 것이 아니고, w를 공통 부분 배열로 가질 수 있는 최소, 최대 인덱스이니, 아래와 같은 접근이 필요하다. 최소 인덱스는 w의 순서대로 문자열의 왼쪽에서 오른쪽으로 sweep하며 최소 등장 위치를 찾고, 최대 인덱스는 w의 역순으로 오른쪽에서 왼쪽으로 sweep하며 찾아나가면 된다. 추후의 계산을 쉽게 하기 위해서 deque를 이용해서 최소는 push_back, 최대는 push+_front 해준다. 

 

pair<deque<int>, deque<int>> trave(string& s, string& w) {
    int sz = size(s);
    int sz2 = size(w);
    deque<int> s_st, s_en;
    s_st.push_back(-1);
    s_en.push_back(sz);
    int idx = 0, idx2 = sz-1;
    for(int i=0; i<sz2; ++i) {
        while(s[idx] != w[i]) ++idx;
        while(s[idx2] != w[sz2-1-i]) --idx2;
        s_st.push_back(idx++);
        s_en.push_front(idx2--);
    }
    return {s_st, s_en};
}

 

 이렇게 하고 나면 아래와 같이 X 문자열에 대해서 left, right 범위를 갖는 변수를, Y문자열에 대해서 left, right 범위를 갖는 변수를 각각 만들고, x배열에서 현재 등장한 문자를 체크하는 x_check, y배열에서 현재 등장한 문자를 체크하는 y_check를 설정한다. 그리고는 w의 각각 알파벳의 범위를 돌면서 가능한 알파벳들을 체크하고 x, y가 같은문자를 가지고 있다면 1을 없다면 0을 출력하게 한다. 주의할 점은 sweeping할 때 최소범위를 갱신하는, 즉 x_check에서 이미 지나간 부분을 먼저 빼주는 것을 먼저 수행해야 한다는 것이며, 경계값 또한 미리 빼 주어 추후에 경계값이 추가되는 것을 미리 방지해야 한다. 이에 따라 x_check와 y_check 배열이 음수가 되는 구간도 생기게 되므로, x_check[i]와 y_check[i]>0인것으로 같은 문자를 가지고 있는지 체크해야 한다.  

 

void solve() {
    cin >> t;
    while(t--) {
        cin >> x >> y >> w;
        auto [x_st, x_en] = trave(x, w);
        auto [y_st, y_en] = trave(y, w);

        int xl =0, xr=0, yl = 0, yr = 0;
        int sz = size(w);
        x_check =y_check= vi(30, 0);
        bool flag = false;
        for(int i=0; i<=sz; ++i) {
            // 축소
            while(xl <= x_st[i]) {
                --x_check[x[xl++]-'a'];
                // ++xl;
            }
            while(yl <= y_st[i]) {
                --y_check[y[yl++]-'a'];
                // ++yl;
            }
            // 확장
            while(xr < x_en[i]) {
                int x_pos = x[xr]-'a';
                ++x_check[x_pos];
                // x_check가 음수로 되는 경우가 생기기 때문에 >0로 잡아야 한다. 
                if(x_check[x_pos]>0 && y_check[x_pos]>0) flag = true;
                ++xr;
            } 
            while(yr < y_en[i]) {
                int y_pos = y[yr]-'a';
                ++y_check[y_pos];
                if(x_check[y_pos]>0 && y_check[y_pos]>0) flag = true;
                ++yr;
            } 
            if(flag) break;
        }
        if(flag) cout << "1\n";
        else cout << "0\n";

    }
}

 

최종 코드를 첨부한다.  최소 최대 인덱스를 구하는 부분과 최종 동일한 알파벳이 있는지 확인하는 부분 모두 sweep하기 때문에 최종 시간 복잡도는 O(t*(|x|+|y|))가 되겠다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <deque>

using namespace std;
#define fastio cin.tie(0)->sync_with_stdio(0)

using ll = long long;
using matrix = vector<vector<ll>>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vb = vector<bool>;

int t;
string x, y, w;
vi x_check, y_check;

pair<deque<int>, deque<int>> trave(string& s, string& w) {
    int sz = size(s);
    int sz2 = size(w);
    deque<int> s_st, s_en;
    s_st.push_back(-1);
    s_en.push_back(sz);
    int idx = 0, idx2 = sz-1;
    for(int i=0; i<sz2; ++i) {
        while(s[idx] != w[i]) ++idx;
        while(s[idx2] != w[sz2-1-i]) --idx2;
        s_st.push_back(idx++);
        s_en.push_front(idx2--);
    }
    return {s_st, s_en};
}

void solve() {
    cin >> t;
    while(t--) {
        cin >> x >> y >> w;
        auto [x_st, x_en] = trave(x, w);
        auto [y_st, y_en] = trave(y, w);

        int xl =0, xr=0, yl = 0, yr = 0;
        int sz = size(w);
        x_check =y_check= vi(30, 0);
        bool flag = false;
        for(int i=0; i<=sz; ++i) {
            // 축소
            while(xl <= x_st[i]) {
                --x_check[x[xl++]-'a'];
                // ++xl;
            }
            while(yl <= y_st[i]) {
                --y_check[y[yl++]-'a'];
                // ++yl;
            }
            // 확장
            while(xr < x_en[i]) {
                int x_pos = x[xr]-'a';
                ++x_check[x_pos];
                // x_check가 음수로 되는 경우가 생기기 때문에 >0로 잡아야 한다. 
                if(x_check[x_pos]>0 && y_check[x_pos]>0) flag = true;
                ++xr;
            } 
            while(yr < y_en[i]) {
                int y_pos = y[yr]-'a';
                ++y_check[y_pos];
                if(x_check[y_pos]>0 && y_check[y_pos]>0) flag = true;
                ++yr;
            } 
            if(flag) break;
        }
        if(flag) cout << "1\n";
        else cout << "0\n";

    }
}

int main() {
    fastio;
    solve();
    return 0;
}