[Kakao]2020 KAKAO BLIND RECRUITMENT - 가사 검색 Java 풀이

import java.util.*;

class Solution {
    public int[] solution(String[] words, String[] queries) {
        Trie[] tries = new Trie[100001];
        
        int[] answer = new int[queries.length];
        
        //Trie 자료구조 생성
        for(String s : words){
            int len = s.length();
            if(tries[len] == null) 
                tries[len] = new Trie();
            tries[len].insert(s);
        }
        
        //Trie 불러오기
        for(int i = 0; i < queries.length; i++){
            int len = queries[i].length();
            if(tries[len] == null)
                answer[i] = 0;            
            else
                answer[i] = tries[len].getCount(queries[i]);            
        }
        
        return answer;
    }
}

class Trie{
    TrieNode pre_Node;  //앞자리부터의 배열
    TrieNode suf_Node;  //뒷자리부터의 배열
    
    Trie(){
        pre_Node = new TrieNode();
        suf_Node = new TrieNode();
    }
    
    public void insert(String word){
        TrieNode pre_Node = this.pre_Node;
        TrieNode suf_Node = this.suf_Node;
        
        for(int i = 0; i< word.length(); i++){
            pre_Node.count++;
            //HashMap의 computeIfAbsent를 사용하여 word(charAt(i))를 주소로 가지고있는 TrieNode를 가지고 온다.
            //만약 null값이 나오면 새로 생성하여 가지고 온다. [c->new TrieNode()]부분
            pre_Node = pre_Node.children.computeIfAbsent(word.charAt(i), c ->new TrieNode());
        }        
        for(int i = word.length()-1; i >= 0; i--){
            suf_Node.count++;
            suf_Node = suf_Node.children.computeIfAbsent(word.charAt(i), c ->new TrieNode());            
        }
    }
    
    public int getCount(String word){
        //맨 앞자리가 '?'면 역방향 배열 아니면 정방향 배열
        if (word.charAt(0) == '?')
            return getCountBack(word);        
        else
            return getCountFront(word);        
    }
    
    //정방향 배열
    public int getCountFront(String word){        
        TrieNode pre_Node = this.pre_Node;
        for(int i = 0; i< word.length(); i++){
            if(word.charAt(i) == '?') break;
            if(!pre_Node.children.containsKey(word.charAt(i))) return 0;
            pre_Node = pre_Node.children.get(word.charAt(i));                
        }
        
        return pre_Node.count;
    }

    //역방향 배열
    public int getCountBack(String word){        
        TrieNode suf_Node = this.suf_Node;
        for(int i = word.length()-1; i >= 0; i--){
            if(word.charAt(i) == '?') break;
            if(!suf_Node.children.containsKey(word.charAt(i))) return 0;
            suf_Node = suf_Node.children.get(word.charAt(i));
        }
        
        return suf_Node.count;
    }
}

class TrieNode{ 
    Map<Character, TrieNode> children; 
    int count; 
    
    TrieNode(){ 
        this.children = new HashMap<>(); 
        this.count = 0; 
    } 
}