[2018 KAKAO BLIND RECRUITMENT 3차] 자동완성

문제풀이

 

 

트라이 연습으로 매우 좋은 문제였다. 마지막에 카운트를 셀때는 조금 방법이 헷갈려서 시간이 걸린것 같다. 아직 트라이가 익숙하지 않아 전에 짰던 코드를 계속 참고하며 짜는데 연습이 좀더 필요한것 같다. 

 

 

카운트를 셀때 count가 1인 경에는 더 내려가서 셀 필요가 없다 그때는 무조건 1개의 경우만 나오므로 

 

소스코드

#include <string>
#include <vector>
#include <iostream>
 
using namespace std;
 
int answer=0;
class Trie{
private:
    int count;//자식 개수
    bool finish;
    Trie* next[26];
public:
    Trie() : finish(false){
        count =0;
        for(int i=0;i<26;i++){
            next[i]=NULL;
        }
    }
    ~Trie(){
        for(int i=0;i<26;i++){
            if(next[i])
                delete next[i];
        }
    }
    void insert(const char* key){
        if((*key)=='\0'){//문자 끝일때
            if(count==1){
                finish=true;
            }
            return;
        }
        
        int cur = (*key)-'a';
        if(!next[cur]){//다음이 NULL
            next[cur] = new Trie();
        }
        next[cur]->count +=1;
        next[cur]->finish =false;
        next[cur]->insert(key+1); //그다음 글자 insert
    }
    void countNum(){
        if(count>0){
            answer += count;
            if(count==1)
                return;
        }
        if(finish){//finish면 끝
            return;
        }
        for(int i=0;i<26;i++){
            if(next[i])
                next[i]->countNum();
        }
    }
};
 
int solution(vector<string> words) {
    
    Trie* trie = new Trie();
    for(int i=0;i<words.size();i++){
        trie->insert(words[i].c_str());
    }
    trie->countNum();
    
    return answer;
}
 
int main(void) {
    cout<<solution({ "go","gone","guild" })<<endl;
}
 

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17685

프로그래머스