[99클럽/코딩테스트 챌린지/C++] (가사 검색) Trie 자료구조를 활용한 가사 검색 문제 해결

문제 링크 : 

https://school.programmers.co.kr/learn/courses/30/lessons/60060

---

문제 상황

카카오 2020 블라인드 채용 문제 중 가사 검색은 단순한 문자열 매칭 문제가 아니라, 효율성 테스트를 통과해야 하는 최적화 문제였습니다. 초기 접근 방식에서 효율성 테스트에 실패했으며, 문제의 원인을 분석한 결과, Trie 자료구조의 필요성과 활용 방식을 배우게 되었습니다.

---

문제 원인

초기에는 단순한 문자열 매칭으로 문제를 접근했지만, 효율성 테스트에서 실패했습니다.

 

1, 단순 문자열 매칭의 시간 복잡도

• 각 쿼리에 대해 모든 단어를 비교하면 최악의 경우 O(Q×W×L)O(Q \times W \times L)O(Q×W×L)로, 효율성 조건을 만족하지 못함.
• QQQ: 쿼리 수, WWW: 단어 수, LLL: 단어 평균 길이.

2, Trie 자료구조에 대한 이해 부족

• 문자열 검색 문제에 특화된 Trie를 활용하면 패턴 매칭을 효율적으로 처리할 수 있음.
• Trie를 사용하지 못해 와일드카드 패턴을 효율적으로 처리하지 못함.

---

해결 방법

1. Trie 자료구조 사용

Trie는 문자열 검색에 최적화된 자료구조로, 접두사 또는 접미사 기반 검색에 매우 적합합니다.
와일드카드 ?가 접두사와 접미사에만 위치한다는 점을 활용하여, 정방향 Trie와 역방향 Trie를 함께 사용했습니다.

• 정방향 Trie: 단어를 그대로 삽입하여, 접두사가 기준인 쿼리를 처리.
• 역방향 Trie: 단어를 뒤집어 삽입하여, 접미사가 기준인 쿼리를 처리.

---

최종 코드

#include <algorithm>
#include <iostream>
#include <tuple>
#include <unordered_map>
#include <vector>

using namespace std;

struct TrieNode
{
    unordered_map<char, TrieNode*> children; // 현재 노드가 가지고 있는 자식 노드
    unordered_map<int, int> wordLength; // 현재 노드가 가지고 있는 단어 길이 갯수들
};
class Trie {
public:
    TrieNode* root;

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

    void insert(const string& word) {
        TrieNode* node = root;
        int length = word.size();

        for (char c : word) {
            node->wordLength[length]++;
            if (node->children.find(c) == node->children.end()) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
    }

    int search(const string& query) {
        TrieNode* node = root;
        int length = query.size();

        // 와일드카드만 있는 경우
        if (query[0] == '?') {
            return node->wordLength[length];
        }

        for (char c : query) {
            if (c == '?') break; // 와일드카드에 도달하면 중지
            if (node->children.find(c) == node->children.end()) {
                return 0; // 패턴에 맞는 단어 없음
            }
            node = node->children[c];
        }

        return node->wordLength[length];
    }
};
vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer;
    
    Trie forwardTrie;
    Trie reverseTrie;
    
    // word를 Trie에 삽입
    for (const string& word : words)
    {
        forwardTrie.insert(word);
        string reversedWord = word;
        reverse(reversedWord.begin(), reversedWord.end());
        reverseTrie.insert(reversedWord);
    }
    
    // 쿼리 결과 캐싱
    unordered_map<string, int> cache;
    
    // queires를 처리
    for (const string& query : queries)
    {
        if (cache.find(query) != cache.end()) {
            answer.push_back(cache[query]); // 캐싱된 결과 반환
            continue;
        }
        int result;
        // 처음에 오늘 단어가 ?가 아니면 처음부터 찾는다.
	    if (query[0] != '?')
	    {
            result = forwardTrie.search(query);
	    }
	    else
	    {
            string reversedQuery = query;
            reverse(reversedQuery.begin(), reversedQuery.end());
            result = reverseTrie.search(reversedQuery);
	    }
        cache[query] = result;
        answer.push_back(result);
    }
    
    return answer;
}

---

배운 점

1, Trie 자료구조의 효율성 : Trie는 접두사 또는 접미사를 기반으로 하는 문자열 검색 문제에서 매우 강력한 도구입니다.

2, 자료형과 구조 설계의 중요성 : 문제를 효율적으로 해결하기 위해 자료형 선택(예: unordered_map)과 구조 설계(정방향/역방향 Trie)가 중요합니다.

3, 효율성을 고려한 설계 : 캐싱을 활용하여 중복 계산을 방지함으로써, 대규모 입력에서도 효율적으로 동작할 수 있었습니다.

---

결론

이번 문제를 통해 문자열 검색 문제를 해결하는 데 필요한 Trie 자료구조의 강력함을 배울 수 있었습니다. 또한, 효율성을 고려한 설계와 디버깅 과정을 통해 문제 해결 능력을 키울 수 있었습니다. 앞으로 유사한 문제에서도 Trie를 적극적으로 활용할 수 있을 것 같습니다. 🚀