프로그래머스 자동완성 c++ // 트라이, 자동완성 결정방법

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

프로그래머스

1. 자동완성 결정방법

1. cnt[node] 배열을 두고,

2. insert하면서 지나갈때마다 cnt[node] +1 하면서 지나간다.

3. cnt가 1이면, 유일한것이다.

 

2. 의사코드

1. 모두 삽입후 이런 상태가 된다.

2. cur을 내려가면서 (한글자씩 보면서) 1을 찾으면 더 들어가지말고(brak), ret를 리턴하면된다.

int find(string& s){
    int ret=0;
    int cur=root; 
    
    for(auto c : s){
        if(cnt[cur]==1) break;
        cur=nxt[cur][c-'a'];
        ret++;
    }

    return ret;

}

3. 공간복잡도 : n * 글자수 // 100000 * 10

 

3. 전체코드

#include <bits/stdc++.h>

int root = 1;
int unused=2;
const int mx=100000 * 10 +5; //!const 해야 배열의 크기로 사용가능!
int nxt[mx][27];
int cnt[mx],chk[mx]; // 중복접두사의 갯수

using namespace std;

void insert(string& s){
    int cur=root;
    for(auto c : s){
        if(nxt[cur][c-'a']==-1){
            nxt[cur][c-'a']=unused++;
        }
        cur=nxt[cur][c-'a'];
        cnt[cur]++;
    }
    chk[cur]=1; 
}
int find(string& s){
    int ret=0;
    int cur=root; 
    
    for(auto c : s){
        if(cnt[cur]==1) break;
        cur=nxt[cur][c-'a'];
        ret++;
    }

    return ret;

}
int solution(vector<string> words) {
    int answer = 0;
    memset(nxt,-1,sizeof(nxt));
    
    for(auto word : words){
        insert(word);
    }
    for(auto word : words){
        answer+=find(word);
        cout<<"\n";
    }
    return answer;
}