Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 문자열 s에서 t와 일치하는 부분 수열 개수 구하기

문제 설명

소문자로만 이루어진 두 문자열 s와 t가 주어집니다. 이때 문자열 s의 부분 수열(subsequence) 중 문자열 t와 정확히 일치하는 것의 개수를 구해야 합니다. 답이 매우 커질 수 있으므로, 결과는 10^9 + 7로 나눈 나머지를 반환합니다.

예를 들어 입력이 s = "abbd", t = "bd"라면 출력은 2가 됩니다. "bd"를 만들 수 있는 부분 수열이 두 가지 존재하기 때문입니다.

  • s[1] 다음에 s[3]을 이어 붙인 경우
  • s[2] 다음에 s[3]을 이어 붙인 경우

해결 전략: 동적 계획법(DP)

이 문제는 대표적인 동적 계획법(Dynamic Programming) 유형으로 해결할 수 있습니다. 핵심 아이디어는 DP 테이블을 활용하여 "t의 앞 j개 문자를 몇 가지 방법으로 만들 수 있는지"를 누적해 가는 것입니다.

배열 table[i]에는 "t의 처음 i개 문자와 일치하는 s의 부분 수열 개수"가 저장됩니다. 문자열 s를 한 글자씩 순회하면서, 현재 글자가 t의 특정 위치 글자와 일치할 때마다 해당 위치의 카운트를 갱신합니다.

알고리즘 단계

  1. 모듈러 값 m을 10^9 + 7로 설정합니다.
  2. t의 길이가 0이면 0을 반환합니다.
  3. t가 s와 완전히 같으면 1을 반환합니다.
  4. t의 길이가 s보다 크면 0을 반환합니다.
  5. (t의 길이 + 1) 크기의 배열 table을 선언하고 0으로 초기화합니다.
  6. table[0] = 1로 설정합니다. 빈 문자열을 만드는 방법은 하나뿐이기 때문입니다.
  7. i를 0부터 s의 길이 - 1까지 순회하며 다음을 반복합니다.
    • 현재 table 상태를 onsave 배열에 복사합니다.
    • j를 0부터 t의 길이 - 1까지 순회하면서, s[i] == t[j]일 때 table[j + 1] = (table[j + 1] mod m + onsave[j] mod m) mod m으로 갱신합니다.

모든 순회가 끝난 뒤 table[t.size()]에 저장된 값이 곧 정답이 됩니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
int solve(string s, string t) {
    int m = 1000000007;
    if (t.size() == 0)
        return 0;
    if (t == s)
        return 1;
    if (t.size() > s.size())
        return 0;
    vector<int> table(t.size() + 1, 0);
    table[0] = 1;
    for (int i = 0; i < s.size(); i++) {
        vector<int> onsave = table;
        for (int j = 0; j < t.size(); j++) {
            if (s[i] == t[j]) {
                table[j + 1] = (table[j + 1] % m + onsave[j] % m) % m;
            }
        }
    }
    return table[t.size()] % m;
}
main(){
    string s = "abbd", t = "bd";
    cout << (solve(s, t));
}

입력

"abbd", "bd"

출력

2

동작 원리 살펴보기

s = "abbd", t = "bd"인 경우를 단계별로 추적해 보면 다음과 같습니다.

  • 초기 상태: table = [1, 0, 0]
  • 'a' 처리: t의 어떤 글자와도 일치하지 않으므로 변화 없음 → [1, 0, 0]
  • 'b' 처리(인덱스 1): t[0]('b')와 일치 → table[1] += table[0] → [1, 1, 0]
  • 'b' 처리(인덱스 2): t[0]과 일치 → table[1] += table[0] → [1, 2, 0]
  • 'd' 처리: t[1]('d')와 일치 → table[2] += table[1] → [1, 2, 2]

최종적으로 table[2] = 2가 되어, "bd"를 만들 수 있는 부분 수열이 정확히 2개임을 확인할 수 있습니다.

시간 및 공간 복잡도

  • 시간 복잡도: O(n × m) — n은 문자열 s의 길이, m은 문자열 t의 길이입니다.
  • 공간 복잡도: O(m) — t의 길이에 비례하는 DP 배열 하나만 사용합니다.