C++로 문자열 S에서 리스트 L의 모든 단어를 연결한 부분 문자열의 시작 인덱스 찾기

문제 개요

문자열 s와 길이가 모두 같은 여러 단어로 이루어진 리스트 words가 주어졌다고 가정해 봅시다. 이때 s 안에서 words에 포함된 각 단어를 정확히 한 번씩 사용하여 연결한(단어 사이에 다른 문자가 끼어 있지 않은) 부분 문자열의 시작 인덱스를 모두 찾아야 합니다.

예를 들어 입력 문자열이 "wordgoodgoodgoodword"이고 words가 ["word", "good"]라면 출력은 [0, 12]입니다. 인덱스 0에서 시작하는 부분 문자열은 "wordgood", 인덱스 12에서 시작하는 부분 문자열은 "goodword"이기 때문입니다.

해결 접근 방법

이 문제는 슬라이딩 윈도우 기법과 해시 맵(빈도 카운트)을 활용하여 효율적으로 해결할 수 있습니다.

1. ok() 헬퍼 메서드 정의

문자열 s, 맵 wordCnt, 단어 길이 n을 매개변수로 받는 ok() 메서드를 정의합니다.

temp 문자열을 준비하고, s의 첫 n개 문자로 채웁니다.
i를 n부터 s의 크기 - 1까지 반복합니다.
- temp의 크기가 n의 배수이면:
  - wordCnt에 temp가 존재하지 않으면 false를 반환합니다.
  - 존재한다면:
    - wordCnt[temp]가 1이면 wordCnt에서 temp를 제거하고 temp를 빈 문자열로 초기화합니다.
    - 그렇지 않으면 wordCnt[temp] 값을 1 감소시키고 temp를 빈 문자열로 초기화합니다.
- temp에 s[i]를 추가합니다.
반복이 끝난 후 남은 temp에 대해서도 동일하게 처리합니다. wordCnt에 없으면 false를 반환하고, 있다면 빈도를 차감합니다.
모든 단어가 소진되어 wordCnt의 크기가 0이면 true를 반환합니다.

2. 메인 메서드(findSubstring) 구현

a 또는 b의 크기가 0이면 빈 배열을 반환합니다.
맵 wordCnt를 만들고 b에 있는 문자열들의 빈도를 저장합니다.
정답을 담을 배열 ans를 선언합니다.
window := 단어 개수 × 단어당 문자 수 로 설정합니다.
temp에 문자열 a의 처음 window개 문자를 복사합니다.
i를 window부터 a의 크기 - 1까지 반복합니다.
- temp의 크기가 window의 배수이면서 ok(temp, wordCnt, b[0].size())가 true이면 ans에 i - window를 삽입합니다.
- temp에 a[i]를 추가합니다.
- temp의 크기가 window보다 커지면 앞에서 한 문자를 제거합니다(슬라이딩 윈도우 유지).
마지막으로 남은 temp에 대해 조건을 검사하여 만족하면 ans에 a.size() - 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 = {"word","good"};
   Solution ob;
   print_vector(ob.findSubstring("wordgoodgoodgoodword", v));
}

입력

"wordgoodgoodgoodword", {"word","good"}

출력

[0, 12]