프로그래머스 자바 카카오 자동완성 (trie 알고리즘)

문제

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

프로그래머스

 

처음에는 그냥 반복문을 통해 문자들을 비교 하고 결과를 출력하면 된다고 생각 하여 1차원 적으로 코딩을 하였습니다만...

class Solution {
    public int solution(String[] words) {

        int answer = 0;
        for (int i=0; i<words.length; i++) {    // 검사하는 문자갯수 만큼
            String word = words[i];
            int cnt = 0;
            String a = "";
            Loop1 :
            while (cnt < word.length()) {   // 검사하는 문자의 char를 하나씩 늘려가면서 검사
                a += String.valueOf(word.charAt(cnt));    // char to String
                if (a.length() == word.length()) {
                    answer += a.length();
                    break;
                }

                for (int j=0; j<words.length; j++) {
                    if (i!=j && words[j].contains(a)) {
                        break;
                    }

                    if (j == words.length-1) {
                        answer += a.length();
                        break Loop1;
                    }
                }
                cnt++;
            }
        }

	return answer;

    }
}

 

 

해당 문제는 Trie 알고리즘을 이용하는 문제였음. Trie를 적용하여 다시 풀어 보았습니다.

go, gone, guild를 검색 한다면 branchSum으로 node 가지수를 사용하여 해당 그림처럼 구성하면 branchSum이 1이 되는 gon, gu단계에서 글자수(cnt)를 출력 하면 될것입니다. 하지만 branchSum만으로는 go를 해결할 수 없기 때문에 isEnd라는 값을 추가 해주어 branchSum이 1이 아니더라도 isEnd값이 true라면 글자수를 추가 해주도록 하겠습니다.

 

class Solution {

    public int solution(String[] words) {

        int answer = 0;
        answer = solve(words);
        return answer;

    }

    public static class Node {
        HashMap<Character, Node> child = new HashMap(); // HashMap()으로 Node를 계속 이어줘서 가지 모양을 이어준다.
        boolean isEnd = false;
        int branchSum = 0;
    }

    public static class Trie {

        Node root;

        public Trie(){
            root = new Node();
        }   

        public void insert(String word){    // node 만들기

            Node current = root;

            for(Character c : word.toCharArray()){
                if(current.child.get(c) == null){
                    Node node = new Node(); // 새로운 child를 이어 주기 위해 Node()새로 생성하여 put으로 넣어준다.
                    current.child.put(c, node); 
                    current = node; // 새로 생성한 Node()를 current로 넣어줘 current를 바꿔준다. 이 Node의 마지막에 isEnd를 true처리.
                }
                else
                    current = current.child.get(c);     // go에서 gone을 추가 할때는 go까지는 기존에 있는 Node를 사용.
            }
            current.isEnd = true;
        }
    }

    public static int makeBranchSum(Node now){

        if(now.isEnd && now.child.isEmpty())
            return now.branchSum = 1;

        for(Node node : now.child.values())
            now.branchSum += makeBranchSum(node);

        if(now.isEnd && !now.child.isEmpty())
            now.branchSum += 1;
        return now.branchSum;
    }

    public static int search(Node now, int cnt){

        int ret = 0;

        if(now.branchSum == 1)
            return cnt;

        for(Node node : now.child.values())
            ret += search(node, cnt + 1);
        if(now.isEnd)
            ret += cnt;

        return ret;
    }

    public static int solve(String[] words){

        Trie trie = new Trie();

        for(int i=0;i<words.length;i++){
            String word = words[i];
            trie.insert(word);
        }
        makeBranchSum(trie.root);
        return search(trie.root, 0);
    }
}