BOJ 31420 : 문자열 - 그래프 매칭

• 문제 링크 : boj.kr/31420
• 난이도 : G1
• 태그 : 투포인터

31420번: 문자열 - 그래프 매칭

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    ll n;
    cin >> n;
    string s;
    cin >> s;
    ll m;
    cin >> m;
    vector<vector<ll>> edge(26, vector<ll>(26, 0));
    for(int i = 0; i < m; i++) {
        string t;
        cin >> t;
        edge[t[0]-'a'][t[1]-'a'] = i+1;
    }
    ll ans = 0;
    for(int i = 0; i < n-1; i++) {
        vector<ll> seq;
        while(i < n-1 && edge[s[i]-'a'][s[i+1]-'a']) {
            seq.emplace_back(edge[s[i]-'a'][s[i+1]-'a']);
            i++;
        }
        vector<ll> cnt(m + 1);
        if(seq.size() < m) {
            continue;
        }
        ll l = 0;
        ll check = 0;
        for(ll r = 0; r < seq.size(); r++) {
            cnt[seq[r]]++;
            if(cnt[seq[r]] == 1) check++;
            if(check == m) {
                while(cnt[seq[l]] > 1) {
                    cnt[seq[l]]--;
                    l++;
                }
                ans += l + 1;
            }
        }
    }
    cout << ans;

    return 0;
}

---

풀이

그래프의 간선에 번호를 매긴다.

문자열을 탐색하며 그래프의 간선에 포함된 조합으로만 이루어진 구간을 찾는다.

 

찾은 구간을 따로 떼어서 보자.

앞에서 간선에 번호를 매겼기 때문에 구간의 길이가 L이라고 했을 때, 간선의 번호로 이루어졌고 길이가 L-1인 수열을 만들 수 있다.

어떠한 부분 수열이 조건을 만족한다는 것은 그 부분 수열에 모든 간선의 번호가 포함되어 있다는 것이다.

 

이제 r은 현재 원소, l은 현재 구간을 포함하고 조건을 만족하는 최댓값으로 하여 값을 구해준다.

r에 따른 l의 최댓값을 구하는 방법은 다음과 같다.

우선 r을 늘려가며 간선의 번호마다 개수를 세어준다. 모든 간선을 세었다면 l을 좁힌다.

l을 늘려가며 간선의 번호에 해당하는 개수를 빼주고, 만약 l에 해당하는 번호의 개수가 1이라면 멈춘다.

이렇게 l을 구하면 r에 해당하는 최소 부분 수열을 찾았으므로, r의 값에 따라 l+1만큼의 조건을 만족하는 부분 수열이 있다는 것을 알 수 있다.

 

l과 r은 찾은 구간의 길이만큼 움직이고, 찾은 구간들의 길이의 합은 N보다 작으므로 $O(N)$의 시간복잡도로 문제를 해결할 수 있다.