[프로그래머스 Level.4] 가사 검색 (2020 KAKAO BLIND RECRUITMENT) (Java)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/60060

프로그래머스

 

 

 

 

코딩테스트 연습 > 2020 KAKAO BLIND RECRUITMENT > 가사 검색

 

 

 

문제 설명

 

 

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

 

친구들로부터 천재 프로그래머로 불리는 "프로도"는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.

그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다.

 

가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요.

 

 

가사 단어 제한사항

• words의 길이(가사 단어의 개수)는 2 이상 100,000 이하입니다.
• 각 가사 단어의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
• 전체 가사 단어 길이의 합은 2 이상 1,000,000 이하입니다.
• 가사에 동일 단어가 여러 번 나올 경우 중복을 제거하고 words에는 하나로만 제공됩니다.
• 각 가사 단어는 오직 알파벳 소문자로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.

 

검색 키워드 제한사항

• queries의 길이(검색 키워드 개수)는 2 이상 100,000 이하입니다.
• 각 검색 키워드의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
• 전체 검색 키워드 길이의 합은 2 이상 1,000,000 이하입니다.
• 검색 키워드는 중복될 수도 있습니다.
• 각 검색 키워드는 오직 알파벳 소문자와 와일드카드 문자인 '?' 로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.
• 검색 키워드는 와일드카드 문자인 '?'가 하나 이상 포함돼 있으며, '?'는 각 검색 키워드의 접두사 아니면 접미사 중 하나로만 주어집니다.
  • 예를 들어 "??odo", "fro??", "?????"는 가능한 키워드입니다.
  • 반면에 "frodo"('?'가 없음), "fr?do"('?'가 중간에 있음), "?ro??"('?'가 양쪽에 있음)는 불가능한 키워드입니다.

 

 

입출력 예

words	queries	result
["frodo", "front", "frost", "frozen", "frame", "kakao"]	["fro??", "????o", "fr???", "fro???", "pro?"]	[3, 2, 4, 1, 0]

 

 

입출력 예에 대한 설명

• "fro??"는 "frodo", "front", "frost"에 매치되므로 3입니다.
• "????o"는 "frodo", "kakao"에 매치되므로 2입니다.
• "fr???"는 "frodo", "front", "frost", "frame"에 매치되므로 4입니다.
• "fro???"는 "frozen"에 매치되므로 1입니다.
• "pro?"는 매치되는 가사 단어가 없으므로 0 입니다.

 

 

 

 

나의 코드

import java.util.*;

class Solution {
    public int[] solution(String[] words, String[] queries) {
        int[] answer = new int[queries.length];
        
        Trie frontTrie = new Trie();
        Trie backTrie = new Trie();
        
        for(String word : words) {
            frontTrie.insert(word);
            backTrie.insert(new StringBuilder(word).reverse().toString());
        }
        
        for(int i=0; i<queries.length; i++) {
            if(queries[i].charAt(0) == '?')
                answer[i] = backTrie.search(new StringBuilder(queries[i]).reverse().toString());
            else
                answer[i] = frontTrie.search(queries[i]);
        }
        
        return answer;
    }
    
    class TrieNode {
        Map<Character, TrieNode> childNodes = new HashMap<>();
        Map<Integer, Integer> lenMap = new HashMap<>();
    }
    
    class Trie {
        TrieNode rootNode = new TrieNode();
        
        void insert(String word) {
            TrieNode thisNode = rootNode;
            for(int i=0; i<word.length(); i++) {
                thisNode.lenMap.put(word.length(), thisNode.lenMap.getOrDefault(word.length(), 0) + 1);
                thisNode = thisNode.childNodes.computeIfAbsent(word.charAt(i), c -> new TrieNode());
            }
        }
        
        int search(String query) {
            TrieNode thisNode = rootNode;
            
            for(int i=0; i<query.length(); i++) {
                if(query.charAt(i) == '?' || i == query.length() - 1)
                    return thisNode.lenMap.getOrDefault(query.length(), 0);
                
                if(!thisNode.childNodes.containsKey(query.charAt(i))) 
                    return 0;
                
                thisNode = thisNode.childNodes.get(query.charAt(i));
            }
            
            return 0;
        }
    }
}

 

풀이

1. 단어를 검색하는 문제로 Trie 자료구조를 떠올리고 문제를 풀었다.
2. 루트 노드부터 시작해서 자식 노드로 뻗어가며 words로 주어진 단어(word) 문자열의 문자들을 넣으며 해당 노드마다 단어 문자열의 전체 길이를 담는다. 다시 루트 노드부터 시작해서 자식 노드로 뻗어가며 queries로 주어진 단어(query)를 탐색해 나아가다 '?'가 나오면 해당 단어(query)의 길이와 같은 길이를 해당 문자가 갖고 있는지 찾아 answer에 담는다.
   중요한 점은 queries로 주어진 query들 중에 '?'가 앞 부분에 있는 것들이 있으므로 Trie에 words의 단어들을 담을 때 단어들을 제대로 넣는 Trie와 단어들을 거꾸로 뒤집어서 넣는 Trie를 만든다. 그리고 주어진 queries로 탐색할 때도 '?'가 앞 부분에 있을 때는 해당 query를 뒤집은 후 단어들을 거꾸로 뒤집어서 넣은 Tire에서 탐색하면 된다.
3. 우선 TrieNode 클래스를 만들고 두 개의 Map을 생성한다. 하나는 key로 단어의 한 글자인 Character를 갖고 value로 다시 TrieNode 객체를 갖는다. 다른 하나는 key로 단어의 길이를 갖고 value로 해당 단어의 길이의 개수를 갖는다.
4. 그리고 Trie 클래스를 만들어 Trie 객체를 생성하면 TrieNode 객체인 rootNode를 생성하도록 한다. 또한, 이 Trie 클래스 내부에 루트 노드부터 자식노드로 뻗어가며 단어를 넣기 위해 insert() 메소드를 구현하고 단어를 다 집어넣은 후에 단어들을 탐색하기 위한 search() 메소드를 구현한다.
5. 단어들을 원래대로 담기 위한 frontTrie 인스턴스를 생성하고 단어들을 뒤집어서 담기 위한 backTrie 인스턴스를 생성한다.
6. 그리고 words를 for문을 돌면서 insert() 메소드를 이용하여 frontTrie와 backTrie에 단어들을 담는다. backTrie에는 word를 StringBuilder로 생성하여 reverse()를 이용하여 단어를 뒤집고 다시 String으로 변환하여 insert()를 실행한다.
7. insert() 메소드에서는 우선 TrieNode를 생성하고 여기에 rootNode를 받은 후에 주어진 word를 for문을 돌면서 해당 단어의 글자들을 rootNode의 childeNodes부터 자식노드로 계속해서 뻗어가며 담아가며 lengthMap에 단어의 길이를 계속해서 담는다.
8. 단어들을 다 담은 후에 queries를 for문을 돌면서 search() 메소드를 이용하여 query에 해당하는 단어의 개수를 answer에 차례로 담는다. query의 첫 글자가 '?'이면 '?'가 앞 부분에 있는 것이므로 query를 뒤집어서 backTrie 인스턴스에서 탐색을 실행한다.
9. search() 메소드에서도 TrieNode를 생성하고 여기에 rootNode를 받은 후에 주어진 query를 for문을 돌린다. query의 글자들을 rootNode의 childNodes에서부터 탐색해 나아가며 만약 childNodes에 해당 글자가 존재하지 않으면 맞는 단어가 없는 것이므로 0을 반환하고 아니라면 계속해서 탐색해 나아간다. 탐색하다가 query의 글자가 '?'가 나오거나 단어의 마지막 글자이면 해당 글자에 query의 길이와 같은 길이가 있는지 해당 글자의 lengthMap에서 찾아 있다면 해당 길이의 단어 개수를 반환하고 없다면 0을 반환하면 된다.
10. queries에 해당하는 개수들을 모두 answer에 담은 후에 answer를 반환한다.