알고리즘(자동 완성)

* 알고리즘

• 트라이

* 로직

• 트라이 구조를 통해 입력된 단어들의 횟수를 카운팅 해놓는다
• 각 단어들을 한 글자씩 검색
  • 해당 글자가 1번만 사용되었다면 이후의 글자도 하나만 존재하기 때문에 해당 사이클 횟수를 리턴
  • 만약 검색하려는 단어의 마지막 글자까지 왔다면 => 해당 단어의 수를 리턴(사이클 횟수와 같음)
• 위 과정을 반복해 답을 누적한다

 

//자동완성
class Trie {
    public NodeInfo root;

    public Trie() {
        this.root = new NodeInfo(' ');
    }

    public void insert(String word) {
        NodeInfo current = root;
        for(int s=0; s<word.length(); ++s){
            char c = word.charAt(s);
            int idx = c - 'a';

            if(current.child[idx] == null)
                current.child[idx] = new NodeInfo(c);

            else
                current.child[idx].usedCnt++;

            current = current.child[idx];
        }
    }

    public int search(String word) {
        NodeInfo current = root;
        int cnt=1;

        for(int s=0; s<word.length(); ++s){
            char c = word.charAt(s);
            int idx = c - 'a';

            if(current.child[idx] != null){
                //마지막 단어라면
                if(s == word.length()-1) return cnt;

                //해당 글자가 1번만 사용되었다면 더이상 내려갈 필요 x
                if(current.child[idx].usedCnt <= 1) {
                    return cnt;
                }
                else {
                    current = current.child[idx];
                }
            }
            cnt++;
        }
        return cnt;
    }
}

class NodeInfo {
    public char ch;
    public int usedCnt;
    public NodeInfo[] child;

    public NodeInfo(char ch) {
        this.ch = ch;
        this.usedCnt = 1;
        this.child = new NodeInfo[26];
    }
}

public class Problem_AutoComplete {

    public static void main(String[] args) {
        String[] words = {"go","gone", "guild"};
        int answer = solution(words);
        System.out.println(answer);
    }

    public static int solution(String[] words) {
        int answer = 0;

        //make trie
        Trie trie = new Trie();
        for(String word : words){
            trie.insert(word);
        }

        //search word
        for(String word : words){
            answer += trie.search(word);
        }

        return answer;
    }
}