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

programmers.co.kr/learn/courses/30/lessons/60060

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

2021-03-01

---

import java.util.Arrays;
 
public class Solution60060 {
    static class TrieNode {
        TrieNode[] next;
        int count;
 
        TrieNode() {
            next = new TrieNode[26];
        }
    }
 
    static class Trie {
        TrieNode root;
        Trie() {
            root = new TrieNode();
        }
 
        void insert(String str) {
            TrieNode node = root;
            for(int i = 0; i < str.length(); i++) {
                int idx = str.charAt(i) - 'a';
                if(node.next[idx] == null) node.next[idx] = new TrieNode();
                node.count++;
                node = node.next[idx];
            }
        }
 
        int contains(String str) {
            TrieNode node = root;
 
            for(int i = 0; i < str.length(); i++) {
                int idx = str.charAt(i) - 'a';
                if(str.charAt(i) == '?') return node.count; // 만약 들어온 값이 ? 이면 바로 count 값을 리턴
                if(node.next[idx] == null) return 0;
                node = node.next[idx];
            }
            return node.count;
        }
    }
 
    public static int[] solution(String[] words, String[] queries) {
        int[] answer = new int[queries.length];
 
        // 조건에 주어진 길이만큼 만든다.
        Trie[] forward = new Trie[10001]; // 앞에서부터 원래대로 insert
        Trie[] backward = new Trie[10001]; // 뒤에서부터 거꾸로 insert
 
        for (String word : words) { // words를 돌면서 각각의 글자들을 길이 별로 insert하는 부분
            StringBuilder sb = new StringBuilder(word);
            int len = sb.length();
            if (forward[len] == null) { // 한 번도 만들어진 적이 없는 길이라면
                forward[len] = new Trie();
                backward[len] = new Trie();
            }
            forward[len].insert(sb.toString()); // 기존 그대로 insert
            backward[len].insert(sb.reverse().toString()); // 거꾸로 insert
        }
 
        for(int i = 0; i < queries.length; i++) { // queries를 돌면서 가사를 검색한다.
            StringBuilder str = new StringBuilder(queries[i]);
            if(forward[str.length()] == null) answer[i] = 0; // 만약 quries에서 주어진 길이가 존재 하지 않는다면 그냥 0
            else if(str.charAt(0) == '?') { // ? 앞에 있는 경우
                answer[i] = backward[str.length()].contains(str.reverse().toString()); // 글자를 reverse해서 backward로 검사한다.
            } else {
                answer[i] = forward[str.length()].contains(str.toString()); // 원래 글자 그대로 forward로 검사한다.
            }
        }
        return answer;
    }
    public static void main(String[] args) {
        String w[] = {"frodo", "front", "frost", "frozen", "frame", "kakao"};
        String q[] = {"fro??", "????o", "fr???", "fro???", "pro?"};
        
        System.out.println(Arrays.toString(solution(w, q)));
    }
}
 

 

#문제풀이

Trie 자료구조를 이용한 문제이다. 하지만 일반적인? (내가 공부해 본) 트라이 자료구조로 풀면 문제 조건을 맞출 수 없는 문제이다.

기존에 아는 방식에서 각각 노드를 count 해주는 방식으로 해볼까 했지만 조건을 만족하지 못하였고, "길이"를 이용한다라는 힌트를 들어서 풀었다.

 

일단, 문제에서 주어진 문자들을 보면 다음과 같다.

{"frodo", "front", "frost", "frozen", "frame", "kakao"}

 

그리고 트라이를 구성했을 때 아래와 같이 구성할 수 있을 것이다. 이 때 만약 queries 중에 "fro??"라는 값이 들어왔다고 해본다. 이 때, 기존 방식처럼 count를 한다면, o의 count는 같은 depth 4개를 가지고 있어서 "fro??"에 해당하는 답은 4가 될 것이다. 하지만 이것은 세면 안되는 frozen까지 센 방식으로, 정답과 틀리다.

 

 

그래서 다시 문제에서 주어진 문자들 중 길이가 같은 것끼리 묶으면 다음과 같다.

{"frodo", "front", "frost", "frozen", "frame", "kakao"}

 

그 중 길이 5를 기준으로 다시 재구성하면 다음과 같다. 이렇게 되면 queries에서 "fro??"라는 문자가 들어와도 count값이 3으로 올바르게 return 될 것이다.

그리고 물음표가 앞에 있는 경우와 뒤에 있는 경우로 두 가지 경우가 존재하므로, 각각 따로 만들어주어야한다. 

 

나머지 trie 자료구조를 이용한 풀이는 주석으로 자세하게 써놨다.