[프로그래머스] 가사 검색 (java)

코딩테스트 연습 - 가사 검색 | 프로그래머스 (programmers.co.kr)

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

어떻게 생각하고 문제를 풀었는가?

HashMap에 각 문자마다 검색될 수 있는 검색 쿼리를 미리 만들어 카운트를 추가함으로써 문제를 해결할 수 있을 것이라고 생각하였지만 호율성 테스트에서 실패하였습니다.

각 문자마다 길이x2-1개의 쿼리가 존재할 수 있기 때문에 상당히 많은 수의 키 값이 HashMap에 삽입되고, 이를 탐색하는 과정에서 많은 시간이 필요합니다.

문제에서 와일드카드 문자 '?'는 중간에 삽입되거나 양쪽에 존재하거나 존재하지 않는 경우는 고려하지 않습니다. 따라서 ?문자들이 접미사로 붙거나 접두사로 붙는 경우만 존재하므로 공통되는 알파벳 순서를 갖는 단어들의 수를 저장한 후 이를 반환함으로서 더 빠르게 답을 찾을 수 있을 것이라고 생각하였습니다. 

코드

import java.util.*;
class Solution {
    public int[] solution(String[] words, String[] queries) {
        Trie[] trieSuffix = new Trie[10001];
        Trie[] triePrefix = new Trie[10001];
        for(String word : words){
            int len = word.length();
            if(trieSuffix[len]==null) trieSuffix[len] = new Trie();
            trieSuffix[len].insert(word);
            String reversed = reverse(word);
            if(triePrefix[len]==null) triePrefix[len] = new Trie();
            triePrefix[len].insert(reversed);
        }
        int[] answer = new int[queries.length];
        for(int i=0; i<answer.length; i++){
            int len = queries[i].length();
            if(queries[i].charAt(0)=='?'){
                if(triePrefix[len]==null) answer[i] = 0;
                else answer[i] = triePrefix[len].find(reverse(queries[i]));
            }else{
                if(trieSuffix[len]==null) answer[i] = 0;
                else answer[i] = trieSuffix[len].find(queries[i]);
            }
        }
        return answer;
    }
    String reverse(String str){
        return (new StringBuilder(str)).reverse().toString();
    }
    class Trie{
        Trie[] childs = new Trie[26];
        int count=0;
        void insert(String word){
            Trie current = this;
            for(char c : word.toCharArray()){
                current.count++;
                int index = c-'a';
                if(current.childs[index]==null) current.childs[index] = new Trie();
                current = current.childs[index];
            }
            current.count++;
        }
        int find(String word){
            Trie current = this;
            for(char c : word.toCharArray()){
                if(c=='?')  return current.count;
                int index = c-'a';
                if(current.childs[index]==null) return 0;  
                current = current.childs[index];
            }
            return current.count;
        }
        
    }
} 

Trie 구조는 같은 접두사를 공유하는 문자들을 저장할 수 있는 트리 자료 구조입니다.

각 알파벳 순서를 의미하는 노드를 두어 순서에 따라 부모-자식간의 관계를 가짐으로서 문자들 간의 공통 접두사를 파악할 수 있습니다. 

자식 노드의 같은 접두사는 부모 노드들로서 표현된다.

모든 쿼리문은 ?로 시작하거나 ?로 끝나는 문자들이므로 각 노드들에 해당 접두사가 카운트된 횟수를 저장한 후 반환하여 ?로 끝나는 쿼리문의 답을 찾을 수 있습니다.

?로 시작하는 쿼리문은 문자열을 반대로 한다면 비슷하게 답을 찾을 수 있습니다.

또한 ?문자는 하나의 문자만 대체할 수 있습니다. 문자열의 길이별로 Trie 구조의 root 노드를 두고 같은 길이를 갖는 Trie에 대해서만 탐색한다면 더 빠르게 답을 찾을 수 있습니다.