프로그래머스 가사검색 c++ // 정석트라이, 단어 길이별 트라이, 접미사 구하는법, 한계

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

프로그래머스

1. 정석트라이

1. 노드기반 트라이 임

원소 : Trie* child, cnt(만족단어갯수)

 

2. 야매 트라이와 비교

1. cur= root(시작점) / nxt==-1 (자식없음) / nxt[cur][c - 'a']= unused++ (자식할당)

2. cur=this / cur->child == nullptr / cur->child[c-'a'] = new Trie();

 

3. 의사코드

1. 길이를 딱 맞춰서 정답을 구해야한다? -> 길이별 트라이! //Trie[10] : 길이 10인 문자만 모아놓은 트라이

2. 삽입하면서 지나는 노드에 cnt+1 하면서 지나감 => 매치된 단어의 갯수가 자동 누적됨.

3. ? 를만난다 -> 더 탐색할필요없이 그때 누적된 단어 갯수 반환하고 끝내면됨

4. ???abc(접미사) 를 구해야함 -> 뒤집은 별도 트라이 선언, 단어도 뒤집어서 삽입, 탐색하면 기존과 동일함!

이 그림을 생각하면서 코드르 짜도록 하자.

 

4. 전체코드

#include <bits/stdc++.h>

using namespace std;

class Trie{
public: //배열0으로초기화, 0으로 초기화
    Trie() : child(), count(0){}
    void insert(string& s){
        Trie* cur = this; //root에서 시작
        for(auto c: s){ //apple추가
            cur->count++;
            if(cur->child[c-'a']==nullptr){ //자식이없으면 만듬
                cur->child[c-'a']=new Trie();
            }
            cur=cur->child[c-'a'];
        }
        cur->count++; //마지막단어
    }
    //s에 해당하는 갯수반환
    int find(string& s){
        Trie* cur = this; //root에서 시작
        for(auto c: s){ //apple찾기
            if(c=='?') return cur->count; //?면, 모든 자식수 반환하면됨.
            if(cur->child[c-'a']==nullptr){ //자식이없으면 끝냄
                return 0;
            }
            cur=cur->child[c-'a'];
        }
        return cur->count;
    }
private:
    Trie* child[26]; //문자종류갯수
    int count;
};

Trie t1[10000]; //정방향트라이 => 접두사검사
Trie t2[10000]; //역방향트라이 => 접미사를 접두사검사로 바꿈

vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int>  answer;
    for(auto word : words){
        t1[word.size()-1].insert(word); //0-idxed
        reverse(word.begin(),word.end());
        t2[word.size()-1].insert(word);
    }
    for(auto query : queries){
        int ret=0;
        if(query[0]!='?'){
            ret+=t1[query.size()-1].find(query);
            answer.push_back(ret);
        }
        else{
            reverse(query.begin(),query.end());
            ret+=t2[query.size()-1].find(query);
            answer.push_back(ret);
        }
        
    }
    return answer;
}

 

5. 한계

중간에 점이 있는경우 오답이 나온다.

해결 : 재귀 트라이를 써야한다.

search(word, index)

https://leetcode.com/problems/design-add-and-search-words-data-structure/description/?source=submission-noac