문자열 s가 주어졌을 때, s에서 만들 수 있는 비어 있지 않은 고유한(서로 다른) 부분 수열의 개수를 구하는 문제입니다. 답이 매우 커질 수 있으므로 최종 결과는 109 + 7로 나눈 나머지를 반환해야 합니다.
예를 들어 입력이 s = "xxy"라면 출력은 5가 됩니다. "x", "xx", "xy", "y", "xxy"의 다섯 가지 부분 수열이 존재하기 때문입니다.
문제 해결 접근 방법
이 문제는 동적 계획법(DP)을 활용하면 O(n) 시간에 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
현재까지 만들 수 있는 총 부분 수열의 개수를 res라고 할 때, 새로운 문자 c를 처리하면 기존의 모든 부분 수열 뒤에 c를 붙인 경우들과 c 자체 하나가 새롭게 추가됩니다. 이때 배열 table[c]에는 지금까지 문자 c로 끝나는 부분 수열의 개수가 저장되어 있으므로, 이전에 이미 세었던 중복 개수만큼 빼주면 됩니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- m := 109 + 7 (모듈러 값)
- n := 문자열 s의 길이
- 크기가 26인 배열 table 정의 (알파벳별로 해당 문자로 끝나는 부분 수열 개수 저장)
- res := 0
- i를 1부터 n까지 반복하며:
- c := s[i-1]에서 'a'의 ASCII 값을 뺀 인덱스
- curr := (res + 1 - table[c] + m) mod m — 새로 추가되는 부분 수열의 개수
- res := (res + curr) mod m — 전체 개수 갱신
- table[c] := (table[c] + curr) mod m — 문자 c로 끝나는 개수 갱신
- res 반환
(res + 1 - table[c] + m)에서 m을 더하는 이유는 뺄셈 과정에서 음수가 되는 것을 방지하기 위함입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
int solve(string s) {
int n = s.size();
vector<int> table(26);
long long res = 0;
for (int i = 1; i <= n; ++i) {
int c = s[i - 1] - 'a';
int curr = (res + 1 - table[c] + m) % m;
res = (res + curr) % m;
table[c] = (table[c] + curr) % m;
}
return res;
}
int main(){
string s = "xxy";
cout << solve(s);
}입력
"xxy"
출력
5
복잡도 분석
시간 복잡도는 문자열을 한 번만 순회하므로 O(n)이며, 공간 복잡도는 크기 26의 배열만 사용하므로 O(1)입니다. 완전 탐색으로 모든 부분 수열을 생성하는 방식(O(2ⁿ))과 비교했을 때 훨씬 효율적인 접근 방법입니다.