[프로그래머스] 가사 검색 / 2020 KAKAO BLIND RECRUITMENT - JAVA

🖇️ 문제 링크

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

친구들로부터 천재 프로그래머로 불리는 "프로도"는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다. 그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다.

https://programmers.co.kr/learn/courses/30/lessons/60060?language=java

 

---

📝 문제 분석

만약 특별한 방법 없이 완전탐색으로 답을 구하고자 한다면 O(가사 개수 * 쿼리 개수 * 쿼리 길이) 정도의 시간 복잡도를 갖기 때문에 효율성 테스트에 통과할 수 없습니다.

시간 복잡도를 줄이기 위해, 입력 받은 가사를 기반으로 트라이 자료구조를 만듭니다.

'?'는 검색 키워드의 앞이나 뒤에만 위치하고 있기 때문에 정방향 트라이와 역방향 트라이 둘 다 만들어 주도록 합니다.

 

void insert(String str, int idx) {
    int len = str.length();
    if(idx == len) return;
    map.put(len, map.getOrDefault(len, 0) + 1);
    int next = str.charAt(idx) - 'a';
    
   	if(children[next] == null) 
        children[next] = new Trie();
    
    children[next].insert(str, idx + 1);
}

트라이에 단어를 입력하는 메서드입니다. 각 트라이노드마다 <문자열 길이, 개수>의 형태로 맵을 만듭니다.

맵에 <5, 2>가 입력되어 있다면, 현재 트라이 노드를 지나갔고 문자열길이 5인 가사가 2개 있다는 의미입니다.

 

 

 

 

---

⌨️ 코드

import java.util.*;

class Solution {
    public int[] solution(String[] words, String[] queries) {
        Trie forward = new Trie();
        Trie backward = new Trie();
        
        for(String word : words) {
            forward.insert(word, 0);
           	backward.insert(reverse(word), 0); 
        }
        
        int idx = 0;
        int[] ans = new int[queries.length];
        
        for(String query : queries) {
            if(query.charAt(0) == '?')
                ans[idx++] = backward.find(reverse(query), 0);
            else
                ans[idx++] = forward.find(query, 0);
        }
        
        return ans;
    }
   	
    String reverse(String str) {
        return new StringBuilder(str).reverse().toString();
    }
}

class Trie {
    Map<Integer, Integer> map = new HashMap<>();
    Trie[] children = new Trie[26];
    
    void insert(String str, int idx) {
        int len = str.length();
        if(idx == len) return;
        map.put(len, map.getOrDefault(len, 0) + 1);
        int next = str.charAt(idx) - 'a';
        
       	if(children[next] == null) 
            children[next] = new Trie();
        
        children[next].insert(str, idx + 1);
    }
    
    int find(String str, int idx) {
        if(str.charAt(idx) == '?')
            return map.getOrDefault(str.length(), 0);
       	
        int next = str.charAt(idx) - 'a';
        if(children[next] == null)
            return 0;
        
        return children[next].find(str, idx + 1);
    }
}

 

 

 

 

Uploaded by Notion2Tistory v1.1.0