문자열 s와 단어 배열 words가 주어졌다고 가정해 보겠습니다. 배열에 포함된 모든 단어는 길이가 서로 같습니다. 우리가 찾아야 할 것은 문자열 s 안에서 words의 각 단어를 정확히 한 번씩 사용해 연결(concatenation)한 부분 문자열이 시작되는 모든 인덱스입니다. 단, 단어 사이에 다른 문자가 끼어 있어서는 안 됩니다.
예를 들어 입력 문자열이 "barfoothefoobarman"이고 words가 ["foo", "bar"]라면 출력은 [0, 9]가 됩니다. 인덱스 0에서 시작하는 "barfoo"와 인덱스 9에서 시작하는 "foobar"가 각 단어를 한 번씩 사용해 만든 연결 문자열이기 때문입니다.
접근 방법
이 문제는 슬라이딩 윈도우(Sliding Window) 기법과 해시 맵(Hash Map)을 조합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 윈도우 크기를 (단어 개수 × 단어 길이)로 고정한 뒤, 각 위치에서 윈도우 내부의 문자열이 주어진 단어들로 정확히 구성되는지 검사하는 것입니다.
ok() 헬퍼 함수
먼저 윈도우 문자열이 조건을 만족하는지 판별하는 ok() 함수를 정의합니다. 이 함수는 문자열 s, 단어 빈도 맵 wordCnt, 단어 하나의 길이 n을 매개변수로 받으며 다음과 같이 동작합니다.
- 임시 문자열 temp를 준비합니다.
- n번째 문자부터 문자열 끝까지 순회하면서, temp의 길이가 n의 배수가 되는 시점마다 temp가 wordCnt에 존재하는지 확인합니다.
- temp가 맵에 없으면 즉시 false를 반환합니다.
- 존재한다면 해당 단어의 빈도를 1 감소시키고(빈도가 1이면 맵에서 삭제), temp를 다시 빈 문자열로 초기화합니다.
- 순회가 끝난 후 마지막으로 남은 temp에 대해서도 동일한 검사를 수행합니다.
- 모든 과정이 끝났을 때 wordCnt가 완전히 비어 있다면 true를 반환합니다. 이는 모든 단어가 정확히 한 번씩 사용되었다는 뜻입니다.
findSubstring 메인 로직
- a 또는 b의 크기가 0이면 빈 배열을 반환합니다.
- 맵 wordCnt를 만들어 b에 있는 단어들의 빈도를 저장합니다.
- 결과를 담을 배열 ans를 선언합니다.
- window := (단어 개수) × (단어 하나의 문자 수)로 계산합니다.
- 문자열 a를 한 글자씩 이동하며 윈도우를 유지하고, 윈도우 크기가 window의 배수일 때 ok()를 호출해 조건을 만족하면 시작 인덱스(i − window)를 ans에 추가합니다.
- temp의 크기가 window를 초과하면 앞에서 한 글자씩 제거해 윈도우 크기를 일정하게 유지합니다.
- 마지막 윈도우까지 검사를 마친 뒤 ans를 반환합니다.
C++ 구현 예제
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
bool ok(string s, unordered_map <string, int> wordCnt, int n){
string temp = "";
for(int i = 0; i < n; i++){
temp += s[i];
}
for(int i = n; i < s.size(); i++){
if(temp.size() % n == 0){
if(wordCnt.find(temp) == wordCnt.end())return false;
else{
if(wordCnt[temp] == 1){
wordCnt.erase(temp);
temp = "";
}
else{
wordCnt[temp]--;
temp = "";
}
}
}
temp += s[i];
}
if(wordCnt.find(temp) == wordCnt.end())return false;
else{
if(wordCnt[temp] == 1){
wordCnt.erase(temp);
temp = "";
}
else{
wordCnt[temp]--;
temp = "";
}
}
return wordCnt.size() == 0;
}
vector<int> findSubstring(string a, vector<string> &b) {
if(a.size() == 0 || b.size() == 0)return {};
unordered_map <string, int> wordCnt;
for(int i = 0; i < b.size(); i++)wordCnt[b[i]]++;
vector <int> ans;
int window = b.size() * b[0].size();
string temp ="";
for(int i = 0; i < window; i++)temp += a[i];
for(int i = window; i < a.size(); i++){
if(temp.size() % window == 0 && ok(temp, wordCnt, b[0].size())){
ans.push_back(i - window);
}
temp += a[i];
if(temp.size() > window)temp.erase(0, 1);
}
if(temp .size() % window ==0 && ok(temp, wordCnt, b[0].size()))ans.push_back(a.size() - window);
return ans;
}
};
main(){
vector<string> v = {"foo", "bar"};
Solution ob;
print_vector(ob.findSubstring("barfoothefoobarman", v));
}입력
"barfoothefoobarman" ["foo", "bar"]
출력
[0, 9]
복잡도 분석
시간 복잡도는 O(N × M × L)입니다. 여기서 N은 문자열의 길이, M은 단어 개수, L은 단어 하나의 길이를 의미합니다. 각 시작 위치에서 윈도우를 M개의 단어로 나누어 해시 맵 조회를 수행하기 때문입니다. 공간 복잡도는 단어 빈도 맵과 임시 문자열 저장을 위해 O(M × L)입니다.