[2020 KAKAO BLIND RECRUITMENT] 가사검색(Trie, Java, 효율성, 간단한 코드)

## 접근

---

- Trie의 add 연산은 간단하나, find 연산은 종료 조건을 분류

* "?" 만나서 종료하는 경우, 존재하지 않은 단어를 만날 경우

 

 

## 효율성

---

- Reverse라는 메소드를 정의해서 사용했는데, 매번 += 연산을 통해서 concat 시켰는데 이게 효율성을 어긋나게 했다.

- ReplaceAll으로 '?'를 대체하는 것대신 '?' 발견 시 종료하도록 코드 구성

 

 

 

## 해설코드

---

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Solution {
    class TrieNode{
        int count;
        TrieNode[] tArr;
        
        TrieNode(){  
            count = 0;
            tArr = new TrieNode[26];
        }
        
        public void add(String s){
            TrieNode trie = this;
            this.count += 1;
            
            for(int i = 0; i < s.length(); i++){
                if(trie.tArr[s.charAt(i) - 'a'] == null)
                    trie.tArr[s.charAt(i) - 'a'] = new TrieNode();
                
                trie = trie.tArr[s.charAt(i) -'a'];
                trie.count += 1;
            }
        }
    }
    
    public int[] solution(String[] words, String[] queries) {
        int[] answer = new int[queries.length];
        TrieNode[][] root = new TrieNode[10001][2];
        
        for(int i = 0; i < words.length; i++){
            if(root[words[i].length()][0] == null){
                root[words[i].length()][0] = new TrieNode();    
                root[words[i].length()][1] = new TrieNode();
            }
            
            root[words[i].length()][0].add(words[i]);
            root[words[i].length()][1].add(new StringBuilder(words[i]).reverse().toString());
        }
        
        for(int i = 0; i < queries.length; i++){
            String stmp = queries[i];
            TrieNode tTmp;
            
            if(root[queries[i].length()][0] == null){
                answer[i] = 0;
                continue;
            }
            
            if(queries[i].charAt(0) != '?'){
                tTmp = root[queries[i].length()][0];
            }else{
                tTmp = root[queries[i].length()][1];
                stmp = new StringBuilder(stmp).reverse().toString();
            }
            
            boolean flag = true;
            for(int j = 0; j < stmp.length(); j++){
                if(stmp.charAt(j) == '?') break;
                       
                if(tTmp.tArr[stmp.charAt(j) -'a'] == null){
                    answer[i] = 0;
                    flag = false;
                    break;
                }
                else
                    tTmp = tTmp.tArr[stmp.charAt(j) - 'a'];
            }
            if(flag) answer[i] = tTmp.count;
        }
        
        return answer;
    }
}