[Programmers] 가사 검색

이 문제는 Trie를 사용하는 문제이다.

words라는 배열을 통해 단어들이 주어지고 거기에서 quries에 해당하는 것을 찾는 것을 보고, Trie 알고리즘 이라는 것을 깨닫게 되었다. 다만 이문제에서는 주의할점이 있다. 효율성을 따지기에 일반적인 Trie로는 시간초과가 생기고 만일 문자 '?'를 만나게 된다면 그즉시 단어의 갯수를 리턴해주는 방식을 사용해야했다. 그리하여 Node 클래스에 멤버변수로 count 라는 함수를 만들어주었고, insert과정에서 위치마다 count를 늘려주었다. 또한 '?'가 붙는 방법이 두가지가 있는데 앞쪽에 붙어 단어를 형성하는 fro?? 같은 것이 있고, 뒤쪽에 붙어 단어를 형성하는 ????o 같은 것이 있다. fro?? 같은 경우는 count를 쉽게 리턴해줄 수 있지만 ????o의 경우는 맨뒤에 o 때문에 즉시 리턴해줄 수 없다. 그렇기에 단어들이 역순으로 저장되어 있는 Trie를 하나 더 설계해주어서 o???? 와 같은 방식으로 볼 수 있게 해주었다. 마지막으로 모든 문자열이 '?'으로 이루어져있는 경우에는 바로 리턴해줄 수 있도록 배열을 하나 생성해 주었다.

이문제는 '?'가 앞쪽이나 뒤쪽에만 올수 있기에 생각보다는 쉽게 풀 수 있던 문제였다.

package programmers2;
 
import java.util.Arrays;
 
public class Solution_2020카카오_가사검색 {
    static class Node{
        boolean isEnd;
        int count;
        Node[] child;
        Node(){
            isEnd=false;count=0;child=new Node[26];
        }
    }
    
    
    public static void main(String[] args) {
        String[] words = {"frodo", "front", "frost", "frozen", "frame", "kakao"};
//        String[] queries= {"fro???"};
        String[] queries= {"fro??", "????o", "fr???", "fro???", "pro?"};
        
        System.out.println(Arrays.toString(solution(words,queries)));
    }
    
    static Node[] root1;
    static Node[] root2;
    
    static int count;
    
    static int[] temp;
    
    static int[] solution(String[] words, String[] queries) {
        root1=new Node[100001];
        root2=new Node[100001];
        temp=new int[100001];
        
        for(String word: words) {
            int len=word.length();
            temp[len]++;
            insert(len,word,false);
            insert(len,reverse(word),true);
        }
        
        int n=queries.length;
        int[] answer=new int[n];
 
        for(int i=0;i<n;i++) {
            count=0;
            String str = queries[i];
            int len =queries[i].length();
            
            if(str.charAt(0)=='?' && str.charAt(len-1)=='?') {
                count=temp[len];
            }else if(str.charAt(len-1)=='?') {    //정방향 root1
                search(root1[len],str);
            }else if(str.charAt(0)=='?') {        //역방향 root2
                search(root2[len], reverse(str));
            }
            
            answer[i]=count;
        }
        
        
        return answer;
    }
    
    static void search(Node root, String str) {
        if(root==null)
            return;
        
        Node cur= root;
        
        for(int i=0;i<str.length();i++) {
            char ch = str.charAt(i);
            
            if(ch=='?') {
                count=cur.count;
                return;
            }else {
                int alp=ch-'a';
                if(cur.child[alp]!=null) {
                    cur=cur.child[alp];
                }else {
                    return;
                }
            }
        }
        
        
    }
    
    static String reverse(String str) {
        return new StringBuilder(str).reverse().toString();
    }
    
    static void insert(int len, String str,boolean reverse) {
        Node cur=null;
        if(reverse==false) {
            if(root1[len]==null) {
                root1[len]=new Node();
            }
            cur=root1[len];
        }else{
            if(root2[len]==null) {
                root2[len]=new Node();
            }
            cur=root2[len];
        }
        
        for(int i=0;i<str.length();i++) {
            int alp=str.charAt(i)-'a';
            
            if(cur.child[alp]==null) {
                cur.child[alp]=new Node();
            }
            cur=cur.child[alp];
            cur.count++;
        }
        cur.isEnd=true;
    }
    
}