2018 - [3차] 자동완성

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

코딩테스트 연습 - [3차] 자동완성

[ 문제풀이 ]

문자열을 검색하는 문제이기 때문에 Trie 자료구조를 사용하면 쉽게 해결할 수 있다. 모든 문자열을 Trie 자료구조에 삽입한 후 다시 모든 문자열에 대해서 query를 하면 된다.

​나는 자식 수를 나타내는 별도의 배열을 추가하여 해결하였다. 자식 수가 1이라는 것은 자신 말고 입력된 문자열이 없다는 것을 의미하기 때문에 다음 문자열까지만 입력하면 자동완성이 된다는 것을 의미한다.

​만약, 마지막 문자열까지 간다면 모든 문자열을 입력해야 한다는 것을 의미한다.

class Trie {
    Node root = new Node(); //root 노드
    
    class Node {
        int[] childCnt;
        Node[] child;

        Node() {
            childCnt = new int[26];
            child = new Node[26];
        }
    }
    
    //문자열을 트라이에 삽입
    void makeTrie(Node root, int idx, String s) {
        if (idx == s.length()) return;
        
        int pos = (int)s.charAt(idx) - 97;
        
        if (root.child[pos] == null) {
            root.child[pos] = new Node();
        }
        root.childCnt[pos]++;
        
        makeTrie(root.child[pos], idx + 1, s);
    }
    
    int query(Node root, int idx, String s) {
    	//마지막 인덱스를 벗어나면 모든 문자열을 입력해야함
        if (idx == s.length()) return idx;
        
        int pos = (int)s.charAt(idx) - 97;
        
        //자식 수가 1인 경우 다음 문자열까지만 입력하면 됨
        if (root.childCnt[pos] == 1) return idx + 1;
        
        return query(root.child[pos], idx + 1, s);
    }
}

class Solution {
    public int solution(String[] words) {
        Trie trie = new Trie();
        
        //모든 문자열 삽입
        for (String s : words) {
            trie.makeTrie(trie.root, 0, s);
        }
        
        int answer = 0;
        //모든 문자열 쿼리
        for (String s : words) {
            answer += trie.query(trie.root, 0, s);
        }
        
        return answer;
    }
}