두 개의 문자열 s1과 s2가 주어졌을 때, s2 안에 s1의 순열(permutation)이 존재하면 true를 반환하는 함수를 작성해야 합니다. 즉, 첫 번째 문자열의 순열 중 하나가 두 번째 문자열의 부분 문자열(substring)로 나타나는지를 판별하는 문제입니다.
예를 들어 s1 = "abc"이고 s2 = "findcab"라고 가정해 보겠습니다. 이 경우 결과는 true가 됩니다. 왜냐하면 "abc"의 순열 중 하나인 "cab"가 s2 안에 그대로 포함되어 있기 때문입니다.
문제 해결 접근 방법
이 문제는 슬라이딩 윈도우(Sliding Window) 기법과 문자 빈도수 카운팅을 조합하여 효율적으로 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.
- 크기가 26인 두 개의 벡터 cnt1과 cnt2를 생성합니다. 각각 s1과 현재 윈도우 내 s2의 알파벳 빈도수를 저장합니다.
- s1의 각 문자를 순회하면서 cnt1[s1[i] - 'a'] 값을 1씩 증가시켜 s1의 문자 빈도수를 기록합니다.
- 포인터 j := 0으로 초기화하고, required := s1의 길이로 설정합니다. required는 아직 매칭되지 않은 필요 문자 수를 의미합니다.
- s2의 길이만큼 i를 순회하며 다음 작업을 반복합니다.
- x := s2[i]로 현재 문자를 가져옵니다.
- cnt2[x - 'a']를 1 증가시켜 윈도우에 문자 x를 추가합니다.
- 만약 cnt1[x - 'a']가 0이 아니고, cnt2[x - 'a'] <= cnt1[x - 'a']라면 required를 1 감소시킵니다. 이는 해당 문자가 아직 필요한 만큼만 들어왔다는 뜻입니다.
- j <= i이면서 cnt2[s2[j] - 'a'] - 1 >= cnt1[s2[j] - 'a']인 동안, 윈도우 왼쪽 끝의 문자가 초과된 경우이므로 cnt2에서 해당 문자 수를 줄이고 j를 1 증가시켜 윈도우를 축소합니다.
- 윈도우 크기(i - j + 1)가 s1의 길이와 같고 required가 0이라면, s1의 순열을 찾은 것이므로 true를 반환합니다.
- 모든 순회가 끝날 때까지 조건을 만족하지 못하면 false를 반환합니다.
C++ 구현 예제
아래 코드를 통해 위 알고리즘이 실제로 어떻게 동작하는지 더 자세히 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool checkInclusion(string s1, string s2) {
vector <int> cnt1(26), cnt2(26);
for(int i = 0; i < s1.size(); i++)cnt1[s1[i] - 'a']++;
int j = 0;
int required = s1.size();
for(int i = 0; i < s2.size(); i++){
char x = s2[i];
cnt2[x - 'a']++;
if(cnt1[x - 'a'] && cnt2[x - 'a'] <= cnt1[x - 'a']) required--;
while(j <= i && cnt2[s2[j] - 'a'] - 1 >= cnt1[s2[j] - 'a']){
cnt2[s2[j] - 'a']--;
j++;
}
if(i - j + 1 == s1.size() && required == 0){
return true;
}
}
return false;
}
};
main(){
Solution ob;
cout << (ob.checkInclusion("abc", "findcab"));
}입력
"abc" "findcab"
출력
1
출력값 1은 true를 의미하며, s2("findcab") 안에 s1("abc")의 순열인 "cab"가 실제로 존재함을 확인할 수 있습니다. 이 알고리즘은 각 문자를 한 번씩만 방문하므로 시간 복잡도는 O(n)이며, 고정 크기(26)의 배열 두 개만 사용하므로 공간 복잡도는 O(1)로 매우 효율적입니다.