문제 개요
문자 a, b, c로만 이루어진 문자열 s가 주어졌을 때, 이 세 문자가 각각 최소 한 번 이상 등장하는 부분 문자열의 개수를 구하는 문제입니다.
예를 들어 문자열이 "abcabc"라면, 조건을 만족하는 부분 문자열은 총 10개입니다.
- 인덱스 0부터 시작: "abc", "abca", "abcab", "abcabc"
- 인덱스 1부터 시작: "bca", "bcab", "bcabc"
- 인덱스 2부터 시작: "cab", "cabc"
- 인덱스 3부터 시작: "abc"
즉, 4 + 3 + 2 + 1 = 10개가 됩니다.
접근 방법: 슬라이딩 윈도우
모든 부분 문자열을 일일이 검사하면 O(n²) 이상의 비용이 듭니다. 대신 슬라이딩 윈도우(Sliding Window) 기법을 사용하면 O(n) 시간에 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다. 오른쪽 끝 i를 하나씩 늘려가면서, 현재 윈도우 [j, i] 안에 a, b, c가 모두 존재하는 한 왼쪽 끝 j를 계속 오른쪽으로 민다고 생각하면 됩니다. while 루프가 끝난 직후에는 윈도우 [j, i]가 조건을 만족하지 않는 상태이므로, 인덱스 i를 오른쪽 끝으로 가지는 유효한 부분 문자열은 시작 위치가 0, 1, ..., j-1인 것들이며 그 개수는 정확히 j개입니다.
알고리즘 단계
- ret := 0으로 초기화하고, 문자별 개수를 저장할 맵 m을 생성한 뒤, j := 0으로 설정합니다.
- i를 0부터 문자열 길이 - 1까지 순회하면서:
- 맵 m에서 s[i]의 개수를 1 증가시킵니다.
- m['a'], m['b'], m['c']가 모두 0보다 큰 동안:
- 맵 m에서 s[j]의 개수를 1 감소시킵니다.
- j를 1 증가시켜 윈도우의 왼쪽 경계를 축소합니다.
- while 루프 종료 후, ret에 j를 더합니다.
- 순회가 끝나면 ret을 반환합니다.
C++ 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numberOfSubstrings(string s) {
int ret = 0;
map <char, int> m;
int j = 0;
for(int i = 0; i < s.size(); i++){
m[s[i]]++;
while(m['a'] > 0 && m['b'] > 0 && m['c'] > 0){
m[s[j]]--;
j++;
}
ret += j;
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.numberOfSubstrings("abcabc"));
}
입력
"abcabc"
출력
10
복잡도 분석
시간 복잡도: O(n) — 포인터 i와 j가 각각 문자열을 최대 한 번씩만 순회하므로 전체 연산 횟수는 선형입니다.
공간 복잡도: O(1) — 맵에는 a, b, c 세 개의 키만 저장되므로 추가 메모리 사용량은 일정합니다.