프로그래머스 가사 검색

·2023년 1월 24일
0

문제

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

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

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


코드

import java.util.*;

class Solution {
    //클래스 생성(현재 노드의 문자, 하위 단어의 수, 하위 노드들을 가진다)
    public static class Node{
        char data;
        int size=0;
        Map<Character, Node> children=new HashMap<>();
        
        public Node(char data){
            this.data=data;
        }
    }
    
    public int[] solution(String[] words, String[] queries) {
        //정방향의 Trie
        Map<Integer, Node> map=new HashMap<>();
        //역방향의 Trie
        Map<Integer, Node> reverseMap=new HashMap<>();
        
        for(String word:words){
            int key=word.length();
            
            //Trie에 해당 문자열의 길이를 기준으로 한 루트 노드가 없으면 생성
            if(!map.containsKey(key)){
                map.put(key, new Node(' '));
                reverseMap.put(key, new Node(' '));
            }
            
            //정방향과 역방향으로 삽입
            insert(word, 0, map.get(word.length()));
            insert(new StringBuilder(word).reverse().toString(), 0, reverseMap.get(word.length()));
        }
        
        int[] answer=new int[queries.length];
        int index=0;
        for(String query:queries){
            //Trie에 없다면 0
            if(!map.containsKey(query.length())){
                answer[index++]=0;
                continue;
            }
            
            //쿼리가 '?'로 시작한다면 역방향 탐색
            if(query.charAt(0)=='?'){
                query=new StringBuilder(query).reverse().toString();
                answer[index++]=find(query, 0, reverseMap.get(query.length()));
            }
            //아니라면 정방향 탐색
            else
                answer[index++]=find(query, 0, map.get(query.length()));
        }
        
        return answer;
    }
    
    //Trie에서 자식노드를 거쳐가며 탐색
    public static int find(String query, int index, Node node){
        //현재 확인해야 하는 쿼리의 문자가 '?'라면 하위 모든 노드를 만족하므로 size 리턴
        if(query.charAt(index)=='?')
            return node.size;
        
        //현재 확인해야 하는 쿼리의 문자와 같은 자식 노드가 없으면 0 리턴
        if(!node.children.containsKey(query.charAt(index)))
            return 0;
        
        //다음 문자 확인
        return find(query, index+1, node.children.get(query.charAt(index)));
    }
    
    //word를 Trie에 삽입하는 메서드
    public static void insert(String word, int index, Node node){
        //해당 word가 거쳐가는 모든 노드에 +1
        node.size++;
        
        //word의 마지막 문자까지 넣었으면 끝
        if(word.length()==index)
            return;
        
        //자식 노드 중에 해당하는 문자의 노드가 없다면 생성
        if(!node.children.containsKey(word.charAt(index)))
            node.children.put(word.charAt(index), new Node(word.charAt(index)));

        //해당하는 문자의 자식 노드로 이동
        insert(word, index+1, node.children.get(word.charAt(index)));
    }
}

해결 과정

  1. 이진 탐색 문제라는 것을 먼저 알고 풀었기 때문에 어디를 이진 탐색으로 해야 하는 지 고민했다. 각 쿼리별로 '?'가 제외된 문자열을 찾을 때 이진 탐색으로 범위를 찾았다. 그리고 선형적으로 ?를 제외한 해당 범위를 탐색했다. 솔직히 '?'의 갯수가 1개밖에 없는 쿼리의 경우 오히려 시간이 더 걸리게 된다.

  2. Trie라는 자료구조에 대해서 알게 됐다. 자동 검색 완성 등에서 쓰이는 자료구조라고 한다. 이를 통해서 단어들을 저장했고, 한 쿼리에 해당하는 문자열의 갯수를 얻으려면 O(log N)으로 가능하다.

  3. 이진 탐색으로 이 문제를 해결하려면 단어를 정렬해두고, 쿼리의 '?'가 아닌 부분으로 시작하는 단어의 처음과 끝 범위를 이진탐색으로 찾으면 된다.

  4. 😁

profile
渽晛

0개의 댓글