프로그래머스 - 자동완성

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

프로그래머스 - 자동완성

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

풀이 : Trie 자료구조(시간 복잡도 : (N*L))를 구현하여 해당 글자에 해당하는 words의 수를 체크 (프로그래머스 - 가사 검색과 유사)
https://velog.io/@jkh2801/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B0%80%EC%82%AC-%EA%B2%80%EC%83%89

class Solution {
    static class Node {
        Node [] arr;
        int cnt;
        Node() {
            this.arr = new Node[26];
        }
    }
    static class Trie {
        Node root;
        Trie() {
            this.root = new Node();
        }
        void insert (String s) {
            Node tempNode = root;
            root.cnt++;
            for (int i = 0; i < s.length(); i++) {
                if(tempNode.arr[s.charAt(i)-'a'] == null) {
                    tempNode.arr[s.charAt(i)-'a'] = new Node();
                    tempNode = tempNode.arr[s.charAt(i)-'a'];
                    tempNode.cnt = 1;
                }else {
                    tempNode = tempNode.arr[s.charAt(i)-'a'];
                    tempNode.cnt++;
                }
            }
        }
        int find (String s) {
            Node tempNode = root;
            for (int i = 0; i < s.length(); i++) {
                if(tempNode.cnt == 1) return i;
                else tempNode = tempNode.arr[s.charAt(i)-'a'];
            }
            return s.length();
        }
    }
    public int solution(String[] words) {
       Trie trie = new Trie ();
        for (String s : words) {
            trie.insert(s);
        }
        int answer = 0;
        for (int i = 0; i < words.length; i++) {
            answer += trie.find(words[i]);
        }
        return answer;
    }
}