프로그래머스 가사 검색 자바 풀이

문제 풀이 시간 : 2시간 12분

문제 요약

?가 포함된 검색 문자열이 단어 목록 중 몇 개와 일치하는지 구하는 문제
?는 알파벳 한 글자를 의미하며 앞 또는 뒤에만 연속으로 등장
예) "fro??" → "fro"로 시작하고 길이가 5인 단어

문제 풀이

이 문제를 처음 봤을 때 제일 먼저 떠오른 건 정규식이었다. 정규식이면 구현도 간단하고 탐색도 꽤 빠르니까 "이걸로 충분하지 않을까?" 싶은 생각이 들었다.

그래서 아래처럼 빠르게 정규식 기반으로 코드를 작성했다.

java

import java.util.*;

class Solution {
    public int[] solution(String[] words, String[] queries) {
        int[] answer = new int[queries.length];
        
        for(int i=0;i<queries.length;i++){
            String now = queries[i];
            StringBuilder reg = new StringBuilder();
            if(now.charAt(0)=='?'){
                int cnt = 0;
                int j= 0;
                for(;j<now.length();j++){
                    if(now.charAt(j)!='?')
                        break;
                    cnt++;
                }
                reg.append("[a-z]{"+cnt+"}");
                reg.append(now.substring(j));
            }
            else{
                int cnt = 0;
                int j = now.length()-1;
                for(;j>=0;j--){
                    if(now.charAt(j)!='?')
                        break;
                    cnt++;
                }
                reg.append(now.substring(0,j+1));
                reg.append("[a-z]{"+cnt+"}");
            }
            
            int sum = 0;
            String t = reg.toString();
            for(int j=0;j<words.length;j++){
                if(words[j].matches(t))
                    sum++;
            }
            answer[i] = sum;
        }
        
        return answer;
    }
}

이 코드는 기능적으로는 전혀 문제 없고 결과도 잘 나온다.

하지만 효율성 테스트에서 통과하지 못한다.

쿼리마다 모든 단어를 정규식으로 매칭해야 하기 때문에 결국 $O(N \times Q)$ 라 시간 초과가 난다.

그래서 다른 방법을 고민하다가, 잊고 있던 자료구조 하나가 떠올랐다.

바로 Trie.

?가 앞 또는 뒤에만 등장한다는 특징만 잘 사용하면 중간 이후는 더 탐색할 필요 없이 해당 지점까지의 단어 길이 빈도만 알면 바로 정답을 구할 수 있다.

그래서 다음과 같은 구조로 해결했다.

일반 Trie → "fro??" 같은 앞부분 고정 쿼리 처리
역방향 Trie → "????o" 같은 뒷부분 고정 쿼리 처리 (단어를 뒤집어서 삽입/탐색)
그리고 Trie의 각 노드마다 len 맵을 둬서 그 노드를 거치는 단어들의 길이별 개수 누적

이렇게 하면 탐색 과정에서 ?가 나오면 곧바로 답을 구할 수 있고, 매 탐색은 단어 길이 범위 안에서만 진행되기 때문에 훨씬 빠르다.

최종 코드

java

import java.util.*;

class Solution {
    public class Node{
        public Map<Character,Node> children;
        public Map<Integer,Integer> len;
        
        public Node(){
            children = new HashMap<>();
            len = new HashMap<>();
        }
    }
    
    public class Trie{
        public Node node;
        
        public Trie(){
            node = new Node();
        }
        
        public void insert(String word){
            Node now = this.node;
            for(int i=0;i<word.length();i++){
                char c = word.charAt(i);
                now.children.putIfAbsent(c,new Node());
                now.len.compute(word.length(),(k,v)->v==null?1:v+1);
                now = now.children.get(c);
            }
        }
        
        public int find(String keyword){
            int ans = 0;
            Node now = this.node;
            
            if(keyword.charAt(0)=='?')
                ans = now.len.getOrDefault(keyword.length(),0);
            if(ans>0)
                return ans;
            
            for(int i=0;i<keyword.length();i++){
                char c = keyword.charAt(i);
                
                if(c=='?')
                    break;
                
                if(!now.children.containsKey(c))
                    return 0;
                
                now = now.children.get(c);
                ans = now.len.getOrDefault(keyword.length(),0);
            }
            return ans;
        }
    }
    
    public int[] solution(String[] words, String[] queries) {
        int n = queries.length;
        int[] answer = new int[n];
        
        Trie trie = new Trie();
        Trie eirt = new Trie();
        
        for(int i=0;i<words.length;i++){
            String word = words[i];
            trie.insert(word);
            eirt.insert(new StringBuilder(word).reverse().toString());
        }
        
        for(int i=0;i<n;i++){
            String keyword = queries[i];
            
            if(keyword.charAt(0)!='?'){
                answer[i] = trie.find(keyword);
            }
            else{
                answer[i] = eirt.find(new StringBuilder(keyword).reverse().toString());
            }
        }
         
        return answer;
    }
}

가사 검색

문제 풀이 시간 : 2시간 12분

문제 요약

문제 풀이

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기