문제 소개
문자열 S가 주어졌을 때, S에서 만들 수 있는 서로 다른 부분 수열(distinct subsequences)의 개수를 구하는 문제입니다. 부분 수열이란 원본 문자열에서 몇 개의 문자를 삭제하거나 그대로 두어 얻을 수 있는 문자열로, 남은 문자들의 상대적인 순서는 유지되어야 합니다.
결과값이 매우 커질 수 있으므로, 정답은 10^9 + 7로 나눈 나머지를 반환해야 합니다.
예를 들어 입력이 "bab"라면 출력은 6입니다. 만들 수 있는 서로 다른 부분 수열은 "a", "b", "ba", "ab", "bb", "bab"의 6가지이기 때문입니다.
풀이 접근 방법
이 문제는 동적 계획법(DP)을 활용하면 문자열을 한 번만 순회하면서 O(n) 시간 안에 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
크기 26의 dp 배열을 사용해 각 알파벳별로 "해당 문자로 끝나는 부분 수열의 개수"를 저장합니다. 문자열을 왼쪽에서 오른쪽으로 한 글자씩 처리하다가 새로운 문자 c를 만나면, 이때 새롭게 추가되는 부분 수열의 개수는 다음과 같이 계산됩니다.
added = (지금까지의 전체 부분 수열 개수 + 1) − (c로 끝나는 기존 부분 수열 개수)
여기서 "+1"은 문자 c 하나만으로 이루어진 새로운 부분 수열을 의미하며, c로 끝나던 기존 개수를 빼는 이유는 같은 문자로 끝나는 중복 수열을 제거하기 위해서입니다.
알고리즘 단계
- 큰 수 연산 시 오버플로우를 방지하기 위해 모듈러 연산용 헬퍼 함수를 정의합니다.
- add(a, b): ((a mod MOD) + (b mod MOD)) mod MOD
- sub(a, b): (((a mod MOD) − (b mod MOD)) + MOD) mod MOD
- mul(a, b): ((a mod MOD) × (b mod MOD)) mod MOD
- 메인 로직은 다음과 같이 진행됩니다.
- n := 문자열 s의 길이
- 크기 26의 dp 배열 선언
- res := 0으로 초기화
- s 앞에 공백을 붙여 인덱스 1부터 순회할 수 있도록 준비
- i := 1부터 n까지 반복:
- x := s[i]
- added := sub(add(res, 1), dp[x − 'a'])
- dp[x − 'a'] := add(dp[x − 'a'], added)
- res := add(res, added)
- res 반환
C++ 구현 코드
아래 예제를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli MOD = 1e9 + 7;
class Solution {
public:
lli add(lli a, lli b){
return ( (a % MOD) + (b % MOD) ) % MOD;
}
lli sub(lli a, lli b){
return ( ( (a % MOD) - (b % MOD) ) + MOD ) % MOD;
}
lli mul(lli a, lli b){
return ( (a % MOD) * (b % MOD) ) % MOD;
}
int distinctSubseqII(string s) {
int n = s.size();
vector<lli> dp(26);
int res = 0;
s = " " + s;
for(lli i = 1; i <= n; i++){
char x = s[i];
int added = sub(add(res, 1) , dp[x - 'a']);
dp[x - 'a'] = add(dp[x - 'a'], added);
res = add(res, added);
}
return res;
}
};
int main(){
Solution ob;
cout << (ob.distinctSubseqII("bab"));
}
입력
"bab"
출력
6
시간 및 공간 복잡도
시간 복잡도: O(n) — 문자열을 한 번만 순회하므로 입력 길이에 비례합니다.
공간 복잡도: O(1) — 알파벳 개수에 해당하는 크기 26의 고정 배열만 사용합니다.