1트

트라이 자료구조를 통해 [3차] 자동완성 문제를 푼지 얼마 지나지 않았기 때문에 트라이 자료구조를 쉽게 떠올릴 수 있었다(문자열의 길이가 100만이기 때문에 브루트 포스로는 어림도 없다)

import java.util.*;

class Solution {
    
   TrieNode root = new TrieNode();
    
    public int[] solution(String[] words, String[] queries) {
        
        int[] answer = new int[queries.length];
        for(String word:words){
            insert(word);
        }
        
        for(int idx=0;idx<queries.length;idx++){
            answer[idx] = getNum(root,queries[idx],0);
        }
        
        
        return answer;
    }
    
		//해당 문자열이 없을 경우 중간에 0으로 return
		//해당 문자열이 존재할 경우 마지막에 isLast가 true이면 1 더해주기
    int getNum(TrieNode node, String word, int idx){
        
        if(node==null) return 0;
        
        if(idx==word.length()){
            //문자 찾았을 경우 1 반환
            if(node.isLast) return 1;
            //아닐경우 0 반환
            return 0;
        }
        int sum = 0;
        if(word.charAt(idx)!='?'){
            TrieNode next = node.child.get(word.charAt(idx));
            if(next==null) return 0;
            sum += getNum(next,word,idx+1);
        }else{
            for(char c='a';c<='z';c++){
                sum += getNum(node.child.get(c),word,idx+1);
            }
        }
        return sum;
        
    }
    
    //트라이 자료구조 만들기
    void insert(String word){
        
        TrieNode node = root;
        
        for(int i=0;i<word.length();i++){
            
            if(node.child.get(word.charAt(i))==null) node.child.put(word.charAt(i),new TrieNode());
            node = node.child.get(word.charAt(i));
        }
        node.isLast = true;
    }
}

class TrieNode{
    
    HashMap<Character,TrieNode> child = new HashMap<>();
    boolean isLast;
}

재귀적으로 모든 트리를 탐색하면서 값을 더하는 방식으로 구현했다

Untitled

효율성에서 낙제점을 받았다…

프로그래머스 LV4 문제를 풀면서 느끼는 것은 오히려 정확성 테스트를 통과하긴 되게 쉽다는 것…

하지만 반면에 효율성 테스트 통과하기는 매우 어렵다는 것…