2020 KAKAO BLIND RECRUITMENT : 가사 검색

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

코딩테스트 연습 - 가사 검색

// 코드

class Solution {
    
    class Trie {
        
        Trie[] child = new Trie[26];
        int count;
        int aLetter = Character.getNumericValue('a'); // 'a' 에 대한 아스키 코드
        
        void insert(String str) {
            Trie curr = this;
            for(char ch : str.toCharArray()) {
                curr.count++;
                int idx = Character.getNumericValue(ch) - aLetter;
                if(curr.child[idx] == null) curr.child[idx] = new Trie();
                
                curr = curr.child[idx];
            }
            curr.count++;
        }
        
        int search(String str) {
            Trie curr = this;
            for(char ch : str.toCharArray()) {
                if(ch == '?') return curr.count;
                curr = curr.child[Character.getNumericValue(ch) - aLetter];
                if(curr == null) return 0;
            }
            return curr.count;
        }
        
    }
    
    Trie[] TrieRoot   = new Trie[10000];
    Trie[] ReTrieRoot = new Trie[10000];
    
    public int[] solution(String[] words, String[] queries) {
        int[] answer = new int[queries.length];
        int ansIdx = 0;
        
        for(String str : words) {
            int idx = str.length() - 1;
            if(TrieRoot[idx] == null) {
                TrieRoot[idx]   = new Trie();
                ReTrieRoot[idx] = new Trie();
            }
            
            TrieRoot[idx].insert(str);
            str = new StringBuilder(str).reverse().toString();
            ReTrieRoot[idx].insert(str);
        }
        
        for(String str : queries) {
            int idx = str.length() - 1;
            if(TrieRoot[idx] == null) {
                answer[ansIdx++] = 0;
                continue;
            }
            
            if(str.charAt(0) != '?') {
                answer[ansIdx++] = TrieRoot[idx].search(str);
            } else {
                str = new StringBuilder(str).reverse().toString();
                answer[ansIdx++] = ReTrieRoot[idx].search(str);
            }
            
        }
        
        return answer;
    }
}