문제 설명
문자열 s와 단어 배열 words가 주어졌다고 가정해 보겠습니다. words에 포함된 모든 단어는 길이가 서로 같습니다. 이때 s 안에서 words의 각 단어를 정확히 한 번씩 사용하고, 그 사이에 다른 문자가 하나도 끼어 있지 않은 상태로 이어 붙인 부분 문자열이 시작되는 모든 인덱스를 찾아야 합니다.
예를 들어 입력 문자열이 "barfoothefoobarman"이고 단어 목록이 ["foo", "bar"]라면 출력은 [0, 9]입니다. 인덱스 0에서 시작하는 부분 문자열은 "barfoo", 인덱스 9에서 시작하는 부분 문자열은 "foobar"로, 두 경우 모두 "foo"와 "bar"를 한 번씩 연결한 결과이기 때문입니다.
알고리즘 접근 방법
이 문제는 슬라이딩 윈도우(sliding window) 기법과 해시 맵(unordered_map)을 조합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 윈도우 크기를 '단어 개수 × 단어 길이'로 고정한 뒤, 윈도우 안의 문자열이 요구 조건을 만족하는지 해시 맵으로 검증하는 것입니다.
1단계: 검증 함수 ok() 정의
- 문자열 s, 단어 빈도 맵 wordCnt, 단어 길이 n을 매개변수로 받는 ok() 함수를 정의합니다.
- s의 앞에서 n글자를 temp에 담습니다.
- i를 n부터 s의 끝까지 순회하며 다음 과정을 반복합니다.
- temp의 길이가 n의 배수라면 하나의 단어가 완성된 것이므로, temp가 wordCnt에 존재하지 않으면 false를 반환합니다.
- temp가 존재하면 wordCnt[temp] 값이 1일 때는 해당 키를 삭제하고, 1보다 크면 값을 1 감소시킨 후 temp를 빈 문자열로 초기화합니다.
- 매 반복마다 temp에 s[i]를 이어 붙입니다.
- 순회가 끝난 뒤 남아 있는 temp에 대해서도 같은 방식으로 검사합니다.
- 모든 단어가 소진되어 wordCnt의 크기가 0이 되면 true를 반환합니다.
2단계: findSubstring() 메서드 구현
- a 또는 b의 크기가 0이면 빈 배열을 반환합니다.
- 맵 wordCnt를 만들어 b에 있는 각 단어의 등장 횟수를 저장합니다.
- 정답을 저장할 배열 ans를 선언합니다.
- window를 '단어 개수 × 각 단어의 길이'로 계산합니다.
- 문자열 a의 첫 window 길이만큼을 temp에 복사합니다.
- i를 window부터 a의 끝까지 순회하며 다음을 수행합니다.
- temp의 길이가 window의 배수이고 ok(temp, wordCnt, b[0].size())의 결과가 참이면 i − window를 ans에 추가합니다.
- temp에 a[i]를 추가한 뒤, temp의 길이가 window를 초과하면 맨 앞 한 글자를 제거해 윈도우 크기를 일정하게 유지합니다.
- 반복이 끝난 후 마지막으로 남은 temp도 검사하여 조건을 만족하면 a.size() − window를 ans에 추가합니다.
- 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));
}입력 및 실행 결과
main 함수에서는 문자열 "barfoothefoobarman"과 단어 벡터 {"foo", "bar"}를 입력으로 사용합니다. 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
[0, 9]출력 결과 [0, 9]는 인덱스 0의 "barfoo"와 인덱스 9의 "foobar", 즉 두 위치에서 조건을 만족하는 부분 문자열이 시작됨을 의미합니다. 이처럼 슬라이딩 윈도우와 해시 맵을 활용하면 가능한 모든 시작 위치를 체계적으로 검사하면서 문제를 해결할 수 있습니다.