문제 링크

내 코드

문자열.

0ms, 23.24MB

class Solution {
public:
    int countPrefixSuffixPairs(vector<string>& words) {
        int answer{};

        for(int i{};i<words.size();++i) {
            for(int j{i + 1};j<words.size();++j) {
                if(words[j].size() < words[i].size()) continue;

                if(chkPrefix(words[i], words[j]) && chkSuffix(words[i], words[j])) ++answer;
            }
        }

        return answer;
    }
    bool chkPrefix(string& s1, string& s2) {
        bool ret{true};
        for(int i{};i<s1.size();++i) {
            if(s1[i] != s2[i]) {
                ret = false; break;
            }
        }
        return ret;
    }
    bool chkSuffix(string& s1, string& s2) {
        bool ret{true};
        for(int i{};i<s1.size();++i) {
            if(s1[s1.size() - i - 1] != s2[s2.size() - i - 1]) {
                ret = false; break;
            }
        }
        return ret;
    }
};

Solution

Approach 1: Brute Force

• 7ms, 23.34MB
• Complexity
  • Let $n$ be the number of words in the input array words, and let $m$ be the average length of the words.
  • Time Complexity: $O(n^2 \cdot m)$
  • Space Complexity: $O(1)$

class Solution {
public:
    int countPrefixSuffixPairs(vector<string>& words) {
        int n = words.size();
        int count = 0;

        // Step 1: Iterate through each pair of words
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                string& str1 = words[i];
                string& str2 = words[j];

                // Step 2: Skip if the first string is larger than the second
                if (str1.size() > str2.size()) continue;

                // Step 3: Check if str1 is both the prefix and suffix of str2
                if (str2.find(str1) == 0 &&
                    str2.rfind(str1) == str2.size() - str1.size()) {
                    ++count;
                }
            }
        }

        // Step 4: Return the total count of prefix-suffix pairs
        return count;
    }
};

GPT

이 코드는 주어진 문자열 리스트에서 “prefix-suffix pairs”를 찾고 개수를 세는 문제를 해결합니다.
즉, 한 단어가 다른 단어의 접두사(prefix)이면서 접미사(suffix)인 경우를 찾아 개수를 세는 알고리즘입니다.

✅ 시간 복잡도: $O(n^2 * m)$
✅ 효율적인 개선 가능: $O(n * m)$ (KMP or Trie 사용 가능)

---

📌 코드 분석

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

int countPrefixSuffixPairs(vector<string>& words) {
    int n = words.size();
    int count = 0;

• n: words 벡터의 크기
• count: prefix-suffix 쌍의 개수를 저장하는 변수

// Step 1: Iterate through each pair of words
for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {

• 이중 루프를 사용하여 모든 (i, j) 쌍을 확인
• i < j이므로 같은 단어끼리는 비교하지 않음

        string& str1 = words[i];
        string& str2 = words[j];

        // Step 2: Skip if the first string is larger than the second
        if (str1.size() > str2.size()) continue;

• str1이 str2보다 길면 str1이 str2의 prefix + suffix가 될 수 없으므로 건너뜀

        // Step 3: Check if str1 is both the prefix and suffix of str2
        if (str2.find(str1) == 0 &&
            str2.rfind(str1) == str2.size() - str1.size()) {
            ++count;
        }

• find(str1) == 0 → str1이 str2의 접두사(prefix)인지 확인
• rfind(str1) == str2.size() - str1.size() → str1이 str2의 접미사(suffix)인지 확인
• 둘 다 참이면 count++ 증가

// Step 4: Return the total count of prefix-suffix pairs
return count;

• 최종적으로 count를 반환

---

📌 예제 실행

입력

vector<string> words = {"abc", "abcabc", "xyz", "xyzxyz"};
Solution sol;
int result = sol.countPrefixSuffixPairs(words);

단계별 실행

문자열 쌍 검사

i	j	words[i]	words[j]	prefix 검사 (find() == 0)	suffix 검사 (rfind() == end)	count 증가?
0	1	”abc"	"abcabc”	✅ “abc”는 접두사	✅ “abc”는 접미사	✅ 증가
0	2	”abc"	"xyz”	❌ “abc”는 접두사 아님	❌	❌
0	3	”abc"	"xyzxyz”	❌	❌	❌
1	2	”abcabc"	"xyz”	❌	❌	❌
1	3	”abcabc"	"xyzxyz”	❌	❌	❌
2	3	”xyz"	"xyzxyz”	✅ “xyz”는 접두사	✅ “xyz”는 접미사	✅ 증가

출력

2  // ("abc", "abcabc") + ("xyz", "xyzxyz")

---

📌 시간 복잡도 분석

1️⃣ 이중 루프 (O(n²))

• 모든 i, j (i < j) 쌍을 비교 $\rightarrow$ $O(n²)$

2️⃣ find() 및 rfind() 함수 (O(m))

• find()와 rfind()는 최악의 경우 $O(m)$ (m은 단어 길이)

총 시간 복잡도

✅ $O(n^2 * m)$ (최악의 경우)

🚀 효율적인 개선 가능 (아래 참고 ⬇️)

---

📌 개선 방법 (O(n * m))

1️⃣ KMP (Knuth-Morris-Pratt) 알고리즘 사용

✅ find()와 rfind() 대신 KMP 알고리즘을 사용하면 O(m) 대신 O(m) (탐색 최적화)
✅ 이중 루프 제거 가능 $\rightarrow$ $O(n * m)$

개선된 코드 (KMP)

class Solution {
public:
    int countPrefixSuffixPairs(vector<string>& words) {
        int n = words.size();
        int count = 0;

        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                string& prefix = words[i];
                string& fullStr = words[j];

                if (prefix.size() > fullStr.size()) continue;

                if (isPrefix(fullStr, prefix) && isSuffix(fullStr, prefix)) {
                    ++count;
                }
            }
        }
        return count;
    }

private:
    bool isPrefix(const string& fullStr, const string& prefix) {
        return fullStr.compare(0, prefix.size(), prefix) == 0;
    }

    bool isSuffix(const string& fullStr, const string& suffix) {
        return fullStr.compare(fullStr.size() - suffix.size(), suffix.size(), suffix) == 0;
    }
};

개선된 코드의 시간 복잡도

✅ isPrefix() 및 isSuffix() $\rightarrow$ $O(m)$
✅ 이중 루프 $\rightarrow$ $O(n^2)$
✅ 총 $O(n * m)$

---

📌 결론

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

• find()와 rfind()를 사용하여 비교 → 느림
• 단어 길이가 길어질수록 비효율적

✅ 개선된 코드 $(O(n * m))$

• isPrefix() 및 isSuffix() 함수를 사용하여 더 빠르게 검사
• KMP나 Trie를 활용하면 추가적인 속도 향상 가능

🚀 추천: $O(n * m)$ 개선 코드 사용! 🚀

---

📌 최종 추천

상황	추천 방법
입력 크기가 작을 때 (n ≤ 1000)	기존 코드 사용 $(O(n^2 * m))$
긴 문자열이 많을 때 (n > 1000)	개선된 isPrefix() & isSuffix() 사용 $(O(n * m))$
매우 큰 데이터셋 (n > 10⁵)	Trie / KMP 활용

🔥 “부분 문자열” 문제는 항상 find()를 쓰지 말고 KMP나 Trie를 고려하자!” 🔥

Approach 2: Dual Trie

• 24ms, 45.86MB
• Complexity
  • Let $n$ be the number of words in the input array words, and let $m$ be the average length of the words.
  • Time Complexity: $O(n^2 \cdot m)$
  • Space Complexity: $O(n \cdot m)$

class Node {
public:
    Node* links[26] = {};

    // Check if the character is present in the current node
    bool contains(char c) { return links[c - 'a'] != NULL; }

    // Insert a new node for the character
    void put(char c, Node* node) { links[c - 'a'] = node; }

    // Get the next node for the character
    Node* next(char c) { return links[c - 'a']; }
};

class Trie {
public:
    Node* root;

    Trie() { root = new Node(); }

    // Insert a word into the Trie
    void insert(string& word) {
        Node* node = root;
        for (char c : word) {
            if (!node->contains(c)) {
                node->put(c, new Node());
            }
            node = node->next(c);
        }
    }

    // Check if the Trie contains a given prefix
    bool startsWith(string& prefix) {
        Node* node = root;
        for (char c : prefix) {
            if (!node->contains(c)) {
                return false;
            }
            node = node->next(c);
        }
        return true;
    }
};

class Solution {
public:
    int countPrefixSuffixPairs(vector<string>& words) {
        int n = words.size();
        int count = 0;

        // Step 1: Iterate over each word
        for (int i = 0; i < n; i++) {
            Trie prefixTrie, suffixTrie;

            // Step 2: Insert the current word into the prefix Trie
            prefixTrie.insert(words[i]);

            // Step 3: Reverse the word and insert it into the suffix Trie
            string revWord = words[i];
            reverse(revWord.begin(), revWord.end());
            suffixTrie.insert(revWord);

            // Step 4: Iterate over all previous words
            for (int j = 0; j < i; j++) {
                // Step 5: Skip words[j] if it is longer than words[i]
                if (words[j].size() > words[i].size()) continue;

                // Step 6: Extract the prefix and reversed prefix of words[j]
                string prefixWord = words[j];
                string revPrefixWord = prefixWord;
                reverse(revPrefixWord.begin(), revPrefixWord.end());

                // Step 7: Check if words[j] is both a prefix and suffix of
                // words[i]
                if (prefixTrie.startsWith(prefixWord) &&
                    suffixTrie.startsWith(revPrefixWord)) {
                    count++;
                }
            }
        }

        // Step 8: Return the total count of valid pairs
        return count;
    }
};

GPT

이 코드는 Trie (트라이) 자료구조를 사용하여 “Prefix-Suffix Pairs” 문제를 해결하는 최적화된 방법을 구현한 것입니다.

🚀 목표:
주어진 words 벡터에서 words[j]가 words[i]의 접두사(prefix) & 접미사(suffix) 둘 다인 경우 (j, i) 쌍을 찾아 개수를 세기

✅ Trie를 사용하여 $O(n * m)$으로 최적화 (기존 $O(n^2 * m)$에서 개선)

---

📌 코드 분석

1️⃣ Trie 자료구조 구현

class Node {
public:
    Node* links[26] = {};  // 알파벳 26개를 위한 배열

    bool contains(char c) { return links[c - 'a'] != NULL; }
    void put(char c, Node* node) { links[c - 'a'] = node; }
    Node* next(char c) { return links[c - 'a']; }
};

• Node 클래스: 각 문자 노드를 저장하는 구조체
• links[26] 배열: 알파벳 26개 저장 (a-z)
• contains(c), put(c, node), next(c) → 트라이에서 문자 검색/추가

class Trie {
public:
    Node* root;
    Trie() { root = new Node(); }

    void insert(string& word) {
        Node* node = root;
        for (char c : word) {
            if (!node->contains(c)) {
                node->put(c, new Node());
            }
            node = node->next(c);
        }
    }

    bool startsWith(string& prefix) {
        Node* node = root;
        for (char c : prefix) {
            if (!node->contains(c)) {
                return false;
            }
            node = node->next(c);
        }
        return true;
    }
};

• insert(): 단어를 Trie에 삽입
• startsWith(): 주어진 prefix가 Trie 내에 존재하는지 검사

---

2️⃣ countPrefixSuffixPairs 함수 (메인 로직)

int countPrefixSuffixPairs(vector<string>& words) {
    int n = words.size();
    int count = 0;

• n: 입력 벡터 words의 크기
• count: Prefix-Suffix Pairs 개수를 저장하는 변수

// Step 1: Iterate over each word
for (int i = 0; i < n; i++) {
    Trie prefixTrie, suffixTrie;

• i번째 단어를 기준으로 접두사 Trie, 접미사 Trie 생성

    // Step 2: Insert the current word into the prefix Trie
    prefixTrie.insert(words[i]);

    // Step 3: Reverse the word and insert it into the suffix Trie
    string revWord = words[i];
    reverse(revWord.begin(), revWord.end());
    suffixTrie.insert(revWord);

• prefixTrie: words[i]를 그대로 삽입 → 접두사(prefix) 탐색용
• suffixTrie: words[i]를 뒤집어서 삽입 → 접미사(suffix) 탐색용

    // Step 4: Iterate over all previous words
    for (int j = 0; j < i; j++) {
        // Step 5: Skip words[j] if it is longer than words[i]
        if (words[j].size() > words[i].size()) continue;

• words[j]가 words[i]보다 길면 접두사+접미사가 될 수 없으므로 continue

        // Step 6: Extract the prefix and reversed prefix of words[j]
        string prefixWord = words[j];
        string revPrefixWord = prefixWord;
        reverse(revPrefixWord.begin(), revPrefixWord.end());

        // Step 7: Check if words[j] is both a prefix and suffix of words[i]
        if (prefixTrie.startsWith(prefixWord) &&
            suffixTrie.startsWith(revPrefixWord)) {
            count++;
        }
    }
}

• prefixTrie.startsWith(prefixWord): words[j]가 words[i]의 접두사인지 확인
• suffixTrie.startsWith(revPrefixWord): words[j]가 words[i]의 접미사인지 확인
• 둘 다 만족하면 count++ 증가

// Step 8: Return the total count of valid pairs
return count;

• 최종적으로 count 반환

---

📌 예제 실행

입력

vector<string> words = {"abc", "abcabc", "xyz", "xyzxyz"};
Solution sol;
int result = sol.countPrefixSuffixPairs(words);

Trie 삽입 & 검색 과정

단어 삽입

• "abc" → prefixTrie, "cba" → suffixTrie
• "abcabc" → prefixTrie, "cbacba" → suffixTrie
• "xyz" → prefixTrie, "zyx" → suffixTrie
• "xyzxyz" → prefixTrie, "zyxzyx" → suffixTrie

단어 검색

i	j	words[j]	words[i]	prefixTrie.startsWith()	suffixTrie.startsWith()	count 증가?
1	0	”abc"	"abcabc”	✅	✅	✅ 증가
3	2	”xyz"	"xyzxyz”	✅	✅	✅ 증가

출력

2  // ("abc", "abcabc") + ("xyz", "xyzxyz")

---

📌 시간 복잡도 분석

1️⃣ Trie 삽입 (insert)

• 한 단어를 Trie에 삽입하는 데 O(m)
• 모든 단어를 삽입하면 O(n * m)

2️⃣ Trie 탐색 (startsWith)

• 접두사 & 접미사 확인 $\rightarrow$ O(m)
• 모든 i, j 쌍을 검사하면 O(n * m)

📌 총 시간 복잡도

✅ $O(n * m)$ (이전 $O(n^2 * m)$보다 개선됨)

---

📌 기존 방식과 비교

방법	시간 복잡도	특징
Brute Force (find())	$O(n^2 * m)$	❌ 느림
KMP 알고리즘	$O(n * m)$	✅ 빠름
Trie 사용 (현재 코드)	$O(n * m)$	✅ 빠름, 효율적

🚀 Trie는 특히 단어가 많고 중복이 많을 때 더 빠름!

---

📌 결론

✅ Trie를 사용하여 $O(n * m)$ 시간 복잡도로 최적화
✅ 기존 $O(n^2 * m)$보다 훨씬 빠름
✅ Trie는 접두사 & 접미사 검색에 매우 효율적

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

상황	추천 방법
작은 데이터 $(n \leq 1000)$	find() 사용
긴 문자열이 많을 때 $(n > 1000)$	KMP 알고리즘
매우 큰 데이터 $(n > 10^5)$	Trie 사용 (현재 코드)

🔥 실제 프로젝트에서 Trie는 강력한 성능 향상을 제공할 수 있음! 🔥