Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++에서 문자열 S의 부분 수열과 일치하는 단어 개수 구하기

문자열 S와 단어들의 사전(words)이 주어졌을 때, S의 부분 수열(subsequence)이 되는 words[i]의 개수를 찾는 문제입니다. 예를 들어 입력이 S = "abcde"이고 사전이 ["a", "bb", "acd", "ace"]라면 출력은 3이 됩니다. 사전 속 세 단어 "a", "acd", "ace"가 모두 S의 부분 수열에 해당하기 때문입니다. 반면 "bb"는 S에서 연속적이지 않게 두 개의 'b'를 찾을 수 없으므로 포함되지 않습니다.

해결 접근 방법

이 문제는 각 단어를 일일이 S와 비교하는 비효율적인 방법 대신, 대기열(queue) 기반 그룹핑 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • 각 단어를 첫 글자를 기준으로 맵(map)에 그룹화합니다.
  • S를 한 글자씩 순회하면서, 현재 글자를 대기 중인 단어들을 꺼내 확인합니다.
  • 단어가 한 글자만 남았다면 매칭에 성공한 것이므로 정답 카운트를 증가시킵니다.
  • 아직 남은 글자가 있다면 첫 글자를 제거하고, 다음 글자를 키로 하는 맵에 다시 삽입합니다.

알고리즘 단계

  • n := words 배열의 크기
  • 맵 m 생성 (char → vector<string>)
  • i를 0부터 words 크기까지 반복하며 words[i]를 m[words[i][0]] 위치에 삽입
  • ans := 0으로 초기화
  • i를 0부터 S의 크기까지 반복
    • x := S[i]
    • x가 맵 m에 존재하면
      • temp := m[x]를 꺼내고 m[x] 삭제
      • j를 0부터 temp 크기까지 반복하며, temp[j]의 길이가 1이면 ans를 1 증가, 그렇지 않으면 temp[j]의 인덱스 1부터 끝까지 부분 문자열을 m[temp[j][1]]에 삽입
  • ans 반환

이 방식은 S를 한 번만 순회하면서 모든 단어의 매칭 여부를 동시에 처리할 수 있어 시간 복잡도 면에서 매우 효율적입니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int numMatchingSubseq(string S, vector<string>& words) {
        int n = words.size();
        map <char, vector <string> > m;
        for(int i = 0; i < words.size(); i++){
            m[words[i][0]].push_back(words[i]);
        }
        int ans = 0;
        for(int i = 0; i < S.size(); i++){
            char x = S[i];
            if(m.find(x) != m.end()){
                vector <string> temp = m[x];
                m.erase(x);
                for(int j = 0; j < temp.size(); j++){
                    if(temp[j].size() == 1){
                        ans++;
                    } else {
                        m[temp[j][1]].push_back(temp[j].substr(1));
                    }
                }
            }
        }
        return ans;
    }
};
int main() {
    Solution ob1;
    string s = "abcde";
    vector<string> v{"a","bb","acd","ace"};
    cout << ob1.numMatchingSubseq(s, v) << endl;
    return 0;
}

입력

S = "abcde"
words = ["a", "bb", "acd", "ace"]

출력

3

동작 원리 상세 설명

코드가 실행되면 다음과 같은 과정으로 진행됩니다.

  1. 초기화 단계에서 맵은 {a: ["a", "acd", "ace"], b: ["bb"]} 형태로 구성됩니다.
  2. S의 첫 글자 'a'를 만나면 대기 중인 "a", "acd", "ace"를 꺼냅니다. "a"는 길이가 1이므로 즉시 매칭 성공(ans = 1), 나머지 두 단어는 "cd", "ce"가 되어 c 키 아래에 저장됩니다.
  3. 'b'를 만나면 "bb"가 "b"가 되어 다시 b 키에 저장됩니다.
  4. 'c'를 만나면 "cd"와 "ce"가 각각 "d", "e"가 되어 d, e 키에 저장됩니다.
  5. 'd'를 만나면 "d"가 매칭 성공(ans = 2), 마지막으로 'e'를 만나 "e"가 매칭 성공하여 최종 결과는 3이 됩니다.

이처럼 각 단어는 자신이 기다리는 다음 문자를 키로 하여 관리되므로, 전체 알고리즘의 시간 복잡도는 O(|S| + Σ|words[i]|)로 계산할 수 있습니다.