문제 링크

내 코드

정렬 후 확인

1ms, 11.4MB

class Solution {
public:
    vector<string> stringMatching(vector<string>& words) {
        sort(begin(words), end(words), [](const string& s1, const string& s2) {
            return s1.length() > s2.length();
        }); // 길이 내림차순 정렬

        vector<string> answer;
        int n = words.size();
        for(int i{1};i<n;++i) {
            for(int j{};j<i;++j) {
                if(words[j].find(words[i]) != string::npos) {
                    answer.push_back(words[i]);
                    break;
                }
            }
        }
        return answer;
    }
};

Solution

Approach 1: Brute Force

• 4ms, 11.32MB
• Complexity
  • Let $n$ be the size of the words array and $m$ be the length of the longest string in words.
  • Time Complexity: $O(m^2 \times n^2)$
  • Space Complexity: $O(1)$

class Solution {
public:
    vector<string> stringMatching(vector<string> &words) {
        vector<string> matchingWords;

        // Iterate through each word in the input list.
        for (int currentWordIndex = 0; currentWordIndex < words.size();
             currentWordIndex++) {
            // Compare the current word with all other words.
            for (int otherWordIndex = 0; otherWordIndex < words.size();
                 otherWordIndex++) {
                if (currentWordIndex == otherWordIndex)
                    continue;  // Skip comparing the word with itself.

                // Check if the current word is a substring of another word.
                if (isSubstringOf(words[currentWordIndex],
                                  words[otherWordIndex])) {
                    // Add it to the result list if true.
                    matchingWords.push_back(words[currentWordIndex]);
                    break;  // No need to check further for this word.
                }
            }
        }

        return matchingWords;
    }

private:
    // Helper function to check if `sub` is a substring of `main`.
    bool isSubstringOf(string &sub, string &main) {
        // Loop through possible starting indices in `main`.
        for (int startIndex = 0; startIndex < main.size(); startIndex++) {
            bool subFits = true;

            // Check if the substring matches from the current start index.
            for (int subIndex = 0; subIndex < sub.size(); subIndex++) {
                if (startIndex + subIndex >= main.size() ||
                    main[startIndex + subIndex] != sub[subIndex]) {
                    subFits = false;  // The substring doesn't match.
                    break;  // No need to continue further for this start index.
                }
            }

            if (subFits) {
                return true;  // Found a match, return true.
            }
        }

        return false;  // No match found.
    }
};

GPT

이 코드는 stringMatching이라는 함수를 구현하여 주어진 문자열 리스트에서 다른 문자열의 부분 문자열인 단어들을 찾는 문제를 해결합니다.

---

📌 코드 설명

1️⃣ stringMatching 함수 (메인 로직)

vector<string> stringMatching(vector<string> &words) {
    vector<string> matchingWords;

• words: 입력 문자열 리스트 (예: ["mass", "as", "hero", "superhero"])
• matchingWords: 부분 문자열인 단어들을 저장할 결과 리스트

// Iterate through each word in the input list.
for (int currentWordIndex = 0; currentWordIndex < words.size();
     currentWordIndex++) {

• currentWordIndex: 현재 검사 중인 단어의 인덱스

    // Compare the current word with all other words.
    for (int otherWordIndex = 0; otherWordIndex < words.size();
         otherWordIndex++) {

• otherWordIndex: 현재 단어(words[currentWordIndex])를 다른 단어(words[otherWordIndex])와 비교

        if (currentWordIndex == otherWordIndex)
            continue;  // Skip comparing the word with itself.

• 자기 자신과 비교하는 것은 필요 없으므로 건너뜀

        if (isSubstringOf(words[currentWordIndex], words[otherWordIndex])) {
            matchingWords.push_back(words[currentWordIndex]);
            break;  // No need to check further for this word.
        }

• isSubstringOf 함수(부분 문자열 여부 검사)를 사용하여 현재 단어가 다른 단어의 부분 문자열이면 결과 리스트에 추가하고 더 이상 비교하지 않고 break.

---

2️⃣ isSubstringOf 함수 (부분 문자열 검사)

bool isSubstringOf(string &sub, string &main) {

• sub: 부분 문자열인지 검사할 단어
• main: 검사 대상 단어 (현재 단어가 이 단어의 부분 문자열인지 확인)

for (int startIndex = 0; startIndex < main.size(); startIndex++) {
    bool subFits = true;

• startIndex: main 문자열에서 sub을 검사할 시작 위치
• subFits: sub이 main의 특정 위치에서 시작하는지 여부

    for (int subIndex = 0; subIndex < sub.size(); subIndex++) {
        if (startIndex + subIndex >= main.size() ||
            main[startIndex + subIndex] != sub[subIndex]) {
            subFits = false;
            break;
        }
    }

• subIndex: sub의 문자 인덱스
• main[startIndex + subIndex]가 sub[subIndex]와 일치하지 않으면 subFits = false로 설정하고 루프 종료

    if (subFits) {
        return true;
    }

• subFits == true라면 sub이 main의 부분 문자열이므로 true 반환

return false;  // No match found.

• 끝까지 검사했는데 부분 문자열이 아니라면 false 반환

---

📌 예제 실행

입력

vector<string> words = {"mass", "as", "hero", "superhero"};
Solution sol;
vector<string> result = sol.stringMatching(words);

각 비교 과정

1. "mass" vs "as" → ❌ "as"는 "mass"의 부분 문자열이지만, 반대가 아님
2. "mass" vs "hero" → ❌
3. "mass" vs "superhero" → ❌
4. "as" vs "mass" → ✅ "as"는 "mass"의 부분 문자열 → 결과 리스트에 추가
5. "hero" vs "mass" → ❌
6. "hero" vs "superhero" → ✅ "hero"는 "superhero"의 부분 문자열 → 결과 리스트에 추가
7. "superhero" vs "mass", "as", "hero" → ❌

출력

["as", "hero"]

---

📌 시간 복잡도 분석

1. 메인 루프 (stringMatching)

   • words.size()를 n이라 하면, 두 개의 중첩된 루프에서 비교 수행 $\rightarrow$ $O(n^2)$

2. isSubstringOf 함수

   • 두 문자열 길이를 각각 m, l이라 하면 최대 $O(ml)$
   • 최악의 경우 m ≈ l ≈ words의 최대 길이일 수 있음 $\rightarrow$ $O(n^2 \cdot m)$

3. 총 시간 복잡도

   • $O(n^2 \cdot m)$ (최악의 경우, m이 크면 매우 비효율적)

---

📌 더 효율적인 방법 $O(n \log n + n \cdot m)$

현재 isSubstringOf 함수가 비효율적이므로 C++의 find 함수를 활용하면 속도를 개선할 수 있습니다.

개선된 코드

class Solution {
public:
    vector<string> stringMatching(vector<string> &words) {
        vector<string> matchingWords;
        sort(words.begin(), words.end(), [](const string &a, const string &b) {
            return a.size() < b.size(); // 짧은 단어부터 검사
        });

        for (int i = 0; i < words.size(); i++) {
            for (int j = i + 1; j < words.size(); j++) {
                if (words[j].find(words[i]) != string::npos) {
                    matchingWords.push_back(words[i]);
                    break;
                }
            }
        }

        return matchingWords;
    }
};

시간 복잡도 분석

1. 정렬 $\rightarrow$ $O(n \log n)$
2. 이중 루프 검사 (find 함수 사용) $\rightarrow$ $O(n \cdot m)$
3. 총 시간 복잡도 $\rightarrow$ $O(n \log n + n \cdot m)$
   ✅ 기존 $O(n^2 \cdot m)$ 보다 훨씬 빠름!

---

📌 결론

✅ 기존 코드 $O(n^2 \cdot m)$

• 이중 루프 + 직접 구현한 부분 문자열 검사 → 비효율적

✅ 개선된 코드 $O(n \log n + n \cdot m)$

• 정렬 후 C++ find() 함수 사용 → 훨씬 빠름!

🔥 find()를 활용한 개선된 코드가 더 효율적이므로 추천! 🔥

Approach 2: KMP Algorithm

• 1ms, 11.73MB
• Complexity
  • Let $n$ be the size of the words array and $m$ be the length of the longest string in words.
  • Time Complexity: $O(m \times n^2)$
  • Space Complexity: $O(m)$

class Solution {
public:
    vector<string> stringMatching(vector<string> &words) {
        vector<string> matchingWords;

        for (int currentWordIndex = 0; currentWordIndex < words.size();
             currentWordIndex++) {
            vector<int> lps = computeLPSArray(words[currentWordIndex]);
            // Compare the current word with all other words.
            for (int otherWordIndex = 0; otherWordIndex < words.size();
                 otherWordIndex++) {
                if (currentWordIndex == otherWordIndex)
                    continue;  // Skip comparing the word with itself.

                // Check if the current word is a substring of another word.
                if (isSubstringOf(words[currentWordIndex],
                                  words[otherWordIndex], lps)) {
                    matchingWords.push_back(words[currentWordIndex]);
                    break;  // No need to check further for this word.
                }
            }
        }

        return matchingWords;
    }

private:
    // Function to compute the LPS (Longest Prefix Suffix) array for the
    // substring `sub`.
    vector<int> computeLPSArray(string &sub) {
        vector<int> lps(sub.size(), 0);  // Initialize the LPS array with 0.
        int currentIndex = 1;            // Start from the second character.
        // Length of the current longest prefix which is also a suffix.
        int len = 0;

        while (currentIndex < sub.size()) {
            if (sub[currentIndex] == sub[len]) {
                len++;  // If the current characters match, extend the prefix.
                lps[currentIndex] = len;  // Store the length of the prefix.
                currentIndex++;
            } else {
                if (len > 0) {
                    len = lps[len - 1];  // Backtrack using LPS array to find a
                                         // shorter match.
                } else {
                    currentIndex++;
                }
            }
        }
        return lps;
    }

    // Function to check if `sub` is a substring of `main` using the KMP
    // algorithm.
    bool isSubstringOf(string &sub, string &main, vector<int> &lps) {
        int mainIndex = 0;  // Pointer for `main`.
        int subIndex = 0;   // Pointer for `sub`.

        while (mainIndex < main.size()) {
            if (main[mainIndex] == sub[subIndex]) {
                subIndex++;
                mainIndex++;
                if (subIndex == sub.size()) return true;  // Found a match.
            } else {
                if (subIndex > 0) {
                    // Use the LPS to skip unnecessary comparisons.
                    subIndex = lps[subIndex - 1];
                } else {
                    mainIndex++;
                }
            }
        }
        return false;  // No match found.
    }
};

GPT

이 코드는 KMP 알고리즘 (Knuth-Morris-Pratt) 을 이용하여 주어진 문자열 리스트에서 다른 문자열의 부분 문자열인 단어들을 찾는 효율적인 방법을 구현합니다.

✅ 기존의 단순한 $O(n^2 \cdot m)$ 탐색을 개선하여 $O(n \cdot m)$ 복잡도를 갖는 KMP 알고리즘을 활용한 코드입니다.

---

📌 코드 분석

1️⃣ stringMatching 함수 (메인 로직)

vector<string> stringMatching(vector<string> &words) {
    vector<string> matchingWords;

    for (int currentWordIndex = 0; currentWordIndex < words.size();
         currentWordIndex++) {
        vector<int> lps = computeLPSArray(words[currentWordIndex]); // LPS 배열 계산

• words[currentWordIndex]가 다른 단어의 부분 문자열인지 확인하기 위해 LPS (Longest Prefix Suffix) 배열을 미리 계산

        for (int otherWordIndex = 0; otherWordIndex < words.size();
             otherWordIndex++) {
            if (currentWordIndex == otherWordIndex)
                continue;  // 자기 자신과 비교하는 경우 건너뛴다.

• words[currentWordIndex]를 words[otherWordIndex]의 부분 문자열로 검사

            if (isSubstringOf(words[currentWordIndex], words[otherWordIndex], lps)) {
                matchingWords.push_back(words[currentWordIndex]);
                break;  // 이미 부분 문자열로 확인되면 더 이상 검사하지 않음
            }

• isSubstringOf (KMP 알고리즘 활용)를 통해 부분 문자열인지 확인
• 부분 문자열이면 matchingWords에 추가 후 바로 break $\rightarrow$ 불필요한 연산 방지

---

2️⃣ computeLPSArray 함수 (LPS 배열 계산)

LPS(Longest Prefix Suffix) 배열은 KMP 알고리즘에서 반복되는 부분 문자열을 효율적으로 건너뛰기 위해 사용됩니다.

vector<int> computeLPSArray(string &sub) {
    vector<int> lps(sub.size(), 0);  // 모든 값을 0으로 초기화
    int currentIndex = 1;            // 인덱스 1부터 시작
    int len = 0;  // 현재까지의 LPS 길이 (가장 긴 접두사이면서 접미사)

• lps[i]는 sub[0:i]까지의 부분 문자열에서 가장 긴 접두사 = 접미사 길이를 저장
• 이전까지의 LPS 값을 활용하여 중복된 비교를 피함

    while (currentIndex < sub.size()) {
        if (sub[currentIndex] == sub[len]) {  
            len++;  // 접두사와 접미사가 일치하는 경우 길이 증가
            lps[currentIndex] = len;
            currentIndex++;
        } else {
            if (len > 0) {
                len = lps[len - 1];  // 이전 LPS 값을 활용하여 backtrack
            } else {
                currentIndex++;  // 일치하는 접두사가 없으면 다음 문자로 이동
            }
        }
    }
    return lps;
}

• 중복 비교를 피하기 위해 이전 LPS 값을 활용하여 이동
• 시간 복잡도: O(m) (m은 sub의 길이)

---

3️⃣ isSubstringOf 함수 (KMP 검색 알고리즘)

bool isSubstringOf(string &sub, string &main, vector<int> &lps) {
    int mainIndex = 0;  // `main`의 현재 위치
    int subIndex = 0;   // `sub`의 현재 위치

• main에서 sub을 검색할 때, 현재 탐색 중인 인덱스(mainIndex, subIndex)를 유지

    while (mainIndex < main.size()) {
        if (main[mainIndex] == sub[subIndex]) {
            subIndex++;
            mainIndex++;
            if (subIndex == sub.size()) return true;  // `sub` 전체가 일치하면 반환
        } else {
            if (subIndex > 0) {
                subIndex = lps[subIndex - 1];  // LPS 배열을 사용해 건너뛰기
            } else {
                mainIndex++;  // 첫 번째 문자부터 불일치하면 다음 문자로 이동
            }
        }
    }
    return false;  // 일치하는 부분 문자열이 없음
}

• LPS 배열을 사용하여 불필요한 비교 없이 검색
• 시간 복잡도: $O(n)$ (n은 main의 길이)

---

📌 예제 실행

입력

vector<string> words = {"mass", "as", "hero", "superhero"};
Solution sol;
vector<string> result = sol.stringMatching(words);

단계별 진행

LPS 배열 계산

1. "mass"의 LPS 배열: [0, 0, 0, 0]
2. "as"의 LPS 배열: [0, 0]
3. "hero"의 LPS 배열: [0, 0, 0, 0]
4. "superhero"의 LPS 배열: [0, 0, 0, 0, 0, 0, 0, 0, 0]

부분 문자열 검사 (KMP)

• "as"는 "mass"의 부분 문자열 → 추가 ✅
• "hero"는 "superhero"의 부분 문자열 → 추가 ✅

출력

["as", "hero"]

---

📌 시간 복잡도 분석

1️⃣ computeLPSArray (LPS 배열 계산)

• O(m), m은 sub의 길이

2️⃣ isSubstringOf (KMP 검색)

• O(n), n은 main의 길이

3️⃣ stringMatching 함수 (전체 실행)

• O(n * m), 여기서 n은 words 리스트 크기, m은 각 단어 길이
• 비교적 큰 입력에서도 효율적으로 동작

총 시간 복잡도: $O(n \cdot m)$ (이전의 $O(n^2 \cdot m)$보다 개선됨)

---

📌 기존 코드와 비교

방법	시간 복잡도	개선 여부
단순 브루트포스 (find())	$O(n^2 \cdot m)$	❌ 느림
KMP (현재 코드)	$O(n \cdot m)$	✅ 빠름

🔥 KMP 알고리즘을 활용하면 문자열 검색을 더욱 효율적으로 수행할 수 있습니다! 🔥

---

📌 결론

✅ $O(n \cdot m)$ 복잡도로 최적화된 KMP 알고리즘을 사용하여 부분 문자열 검색
✅ 기존의 $O(n^2 \cdot m)$ 방식보다 훨씬 빠름
✅ 큰 입력에서도 효율적

Approach 3: Suffix Trie

• 22ms, 27.56MB
• Complexity
  • Let $n$ be the size of the words array and $m$ be the length of the longest string in words.
  • Time Complexity: $O(m^2 \times n)$
  • Space Complexity: $O(m^2 \times n)$

class Solution {
public:
    vector<string> stringMatching(vector<string>& words) {
        vector<string> matchingWords;
        TrieNode* root = new TrieNode();  // Initialize the root of the Trie.

        // Insert all suffixes of each word into the Trie.
        for (const auto& word : words) {
            for (int startIndex = 0; startIndex < word.size(); startIndex++) {
                // Insert each suffix starting from index `startIndex`.
                insertWord(root, word.substr(startIndex));
            }
        }

        // Check each word to see if it exists as a substring in the Trie.
        for (auto word : words) {
            if (isSubstring(root, word)) {
                matchingWords.push_back(word);
            }
        }

        return matchingWords;
    }

private:
    class TrieNode {
    public:
        // Tracks how many times this substring appears in the Trie.
        int frequency;
        // Maps characters to their respective child nodes.
        unordered_map<char, TrieNode*> childNodes;
    };

    // Function to insert a word (or suffix) into the Trie.
    void insertWord(TrieNode* root, const string& word) {
        TrieNode* currentNode = root;
        for (char c : word) {
            // If the character already exists as a child node, move to it.
            if (currentNode->childNodes.find(c) !=
                currentNode->childNodes.end()) {
                currentNode = currentNode->childNodes[c];
                // Increment the frequency of the node.
                currentNode->frequency++;
            } else {
                // If the character does not exist, create a new node.
                TrieNode* newNode = new TrieNode();
                // Initialize the frequency to 1.
                newNode->frequency = 1;
                // Add the new node as a child.
                currentNode->childNodes[c] = newNode;
                currentNode = newNode;  // Move to the new node.
            }
        }
    }

    // Function to check if a word exists as a substring in the Trie.
    bool isSubstring(TrieNode* root, string& word) {
        TrieNode* currentNode = root;  // Start from the root node.
        for (char c : word) {
            // Traverse the Trie following the characters of the word.
            currentNode = currentNode->childNodes[c];
        }
        // A word is a substring or a different string if its frequency in the
        // Trie is greater than 1.
        return currentNode->frequency > 1;
    }
};

GPT

이 코드는 Trie (트라이) 자료구조를 활용하여 부분 문자열을 효율적으로 검색하는 방법을 구현한 것입니다. 기존의 $O(n^2 \cdot m)$ 시간 복잡도를 갖는 브루트포스 방식보다 개선된 $O(n \cdot m)$ 시간 복잡도를 갖습니다.

---

📌 코드 설명

1️⃣ stringMatching 함수 (메인 로직)

vector<string> stringMatching(vector<string>& words) {
    vector<string> matchingWords;
    TrieNode* root = new TrieNode();  // Trie의 루트 노드 생성

• matchingWords: 부분 문자열인 단어들을 저장할 벡터
• root: Trie의 루트 노드 (모든 단어의 접미사를 저장)

// Insert all suffixes of each word into the Trie.
for (const auto& word : words) {
    for (int startIndex = 0; startIndex < word.size(); startIndex++) {
        insertWord(root, word.substr(startIndex)); // 각 접미사를 Trie에 삽입
    }
}

• 각 단어의 모든 접미사(suffix)를 Trie에 저장
• word.substr(startIndex): startIndex에서 시작하는 부분 문자열을 Trie에 삽입
  • 예: "hero" → 삽입할 접미사: ["hero", "ero", "ro", "o"]

// Check each word to see if it exists as a substring in the Trie.
for (auto word : words) {
    if (isSubstring(root, word)) {
        matchingWords.push_back(word);
    }
}

• Trie를 탐색하여 word가 부분 문자열로 존재하는지 확인
• 존재하면 matchingWords 벡터에 추가

---

2️⃣ TrieNode 클래스

class TrieNode {
public:
    int frequency;  // 해당 노드를 몇 번 방문했는지 (부분 문자열 등장 횟수)
    unordered_map<char, TrieNode*> childNodes;  // 자식 노드 저장
};

• frequency: 해당 부분 문자열이 Trie에서 몇 번 등장했는지 저장
• childNodes: 자식 노드를 저장하는 unordered_map<char, TrieNode*>
  • 각 문자마다 새로운 TrieNode를 생성하여 연결

---

3️⃣ insertWord 함수 (Trie에 접미사 삽입)

void insertWord(TrieNode* root, const string& word) {
    TrieNode* currentNode = root;
    for (char c : word) {
        if (currentNode->childNodes.find(c) != currentNode->childNodes.end()) {
            currentNode = currentNode->childNodes[c];
            currentNode->frequency++;  // 해당 노드의 방문 횟수 증가
        } else {
            TrieNode* newNode = new TrieNode();
            newNode->frequency = 1;
            currentNode->childNodes[c] = newNode;
            currentNode = newNode;
        }
    }
}

• Trie를 따라가며 문자가 존재하면 이동하고, 없으면 새로운 노드를 생성
• frequency++: 이 노드가 몇 번 등장했는지 기록

예제 실행 ("hero")

h → e → r → o
   → r → o
      → o

이렇게 "hero"의 모든 접미사가 Trie에 저장됨.

---

4️⃣ isSubstring 함수 (부분 문자열 확인)

bool isSubstring(TrieNode* root, string& word) {
    TrieNode* currentNode = root;
    for (char c : word) {
        currentNode = currentNode->childNodes[c];  // Trie를 따라감
    }
    return currentNode->frequency > 1;  // Trie에서 2번 이상 등장한 경우 부분 문자열
}

• Trie에서 word를 찾고, 해당 노드의 frequency 값이 1보다 크면 부분 문자열
• 즉, 다른 단어의 일부로 여러 번 등장했는지 체크

---

📌 예제 실행

입력

vector<string> words = {"mass", "as", "hero", "superhero"};
Solution sol;
vector<string> result = sol.stringMatching(words);

Trie 구성 과정

1. "mass" → "mass", "ass", "ss", "s"
2. "as" → "as", "s"
3. "hero" → "hero", "ero", "ro", "o"
4. "superhero" → "superhero", "uperhero", "perhero", "erhero", "rhero", "hero", "ero", "ro", "o"

Trie에 "as", "hero"가 여러 번 등장함 → matchingWords = ["as", "hero"]

출력

["as", "hero"]

---

📌 시간 복잡도 분석

1️⃣ Trie 구축 (insertWord)

• 각 단어의 모든 접미사를 삽입 → $O(n \cdot m)$ (최악의 경우 m(m+1)/2 개의 접미사)
• 단어 길이 m, 단어 개수 n이므로 평균 $O(n \cdot m)$

2️⃣ 부분 문자열 검색 (isSubstring)

• Trie에서 단어 검색 $\rightarrow$ O(m) (최대 m번 문자 비교)

📌 총 시간 복잡도

• $O(n \cdot m)$ $\rightarrow$ KMP와 동일한 수준의 성능, 하지만 실제로는 상수 계수가 작아서 더 빠를 수도 있음!

---

📌 기존 방식과 비교

방법	시간 복잡도	특징
브루트포스 (find())	$O(n^2 \cdot m)$	❌ 느림
KMP 알고리즘	$O(n \cdot m)$	✅ 빠름
Trie 사용 (현재 코드)	$O(n \cdot m)$	✅ 빠름, 부분 문자열 탐색 최적화

🚀 Trie 방식은 특히 단어 수가 많고, 중복된 접미사가 많을 때 효율적!

---

📌 결론

✅ Trie를 사용하여 $O(n \cdot m)$ 시간 복잡도로 부분 문자열 검색 최적화
✅ 각 단어의 접미사를 Trie에 저장하여 효율적인 탐색 가능
✅ KMP와 유사한 성능을 내면서도, 다량의 문자열에서 더 빠를 수 있음

---

🔥 어떤 방식이 가장 좋은가?

상황	추천 방법
작은 데이터 (n ≤ 1000)	브루트포스 (find())
긴 문자열이 많을 때	KMP 알고리즘
중복된 접미사가 많을 때	Trie 사용 (현재 코드)

💡 Trie는 단순한 KMP보다 실전에서 더 좋은 성능을 낼 가능성이 높습니다!