[2020 KAKAO BLIND RECRUITMENT] 가사 검색

2020 KAKAO BLIND RECRUITMENT 가사 검색

유형

• Trie
• Regex

문제 풀이를 위해, 카카오 공식 문제 해설과 다른 분들의 풀이를 참고하였다.

정확성 테스트를 통과하기 위해서는, regex를 사용하면 되는 간단한 문제였지만,
효율성 테스트를 통과하기 위해서는, Trie 구조를 사용해야 하는 쉽지 않은 문제였다.

또한, Trie 구조에서 삽입이나 검색 연산을 할 경우, recursive로 함수를 짤 경우에는 timeout이 났기 때문에, iterative로 모든 연산을 변환해주는 것도 필요한 문제였다.

코드

정확성 테스트 통과 (REGEX 사용)

// regex 이용 : 정확성 Test만 통과
class Solution {
    public int[] solution(String[] words, String[] queries) {
        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            queries[i] = queries[i].replace("?", "\\S");
            for (int j = 0; j < words.length; j++) {
                if (words[j].matches(queries[i])) answer[i]++;
            }
        }

        return answer;
    }
}

정확성/효율성 테스트 통과 (TRIE 사용)

import java.util.ArrayList;
import java.util.List;

class Solution {
    final int ALPHABET_SIZE = 26; // a-z는 26개
    
    class Trie {
        Trie[] child = new Trie[ALPHABET_SIZE];
        int childNum = 0;

        // 효율성 테스트를 통과하기 위해서는 recursive(재귀)가 아닌 iterative로 풀어야 한다.
        public void add(String word) {
            Trie current = this;
            for(char c: word.toCharArray()) {
                current.childNum++;
                int alphabetIndex = getAlphabetIndex(c);
                if(current.child[alphabetIndex] == null) {
                    current.child[alphabetIndex] = new Trie();
                }
                current = current.child[alphabetIndex];
            }
        }

        public int find(String query) {
            Trie current = this;
            for(char c: query.toCharArray()) {
                if (c == '?') {
                    return current.childNum;
                }
                int alphabetIndex = getAlphabetIndex(c);
                if (current.child[alphabetIndex] == null) {
                    return 0;
                } else {
                    current = current.child[alphabetIndex];
                }
            }
            return this.childNum;
        }
    }

    private int getAlphabetIndex(char alphabet) {
        return alphabet - 'a';
    }

    List<Integer> answer = new ArrayList<>();

    // Trie 이용 : 정확성과 효율성 Test 통과
    public int[] solution(String[] words, String[] queries) {
        // 1. 문자 길이 별로 Trie를 만들어준다.
        // 2. 정방향, 역방향 별로 Trie를 만들어준다.
        Trie[] front = new Trie[10001];
        Trie[] back = new Trie[10001];

        for (String word: words) {
            int len = word.length();
            if(front[len] == null) {
                front[len] = new Trie();
                back[len] = new Trie();
            }
            front[len].add(word);
            back[len].add(reverse(word));
        }

        for (String query: queries) {
            int len = query.length();
            int cnt;
            
            if(front[len] == null) {
                cnt = 0;
            }
            else if (query.startsWith("?")) {
                cnt = back[len].find(reverse(query));
            }
            else {
                cnt = front[len].find(query);
            }
            answer.add(cnt);
        }

        return answer.stream().mapToInt(i->i).toArray();
    }

    private String reverse(String word) {
        return new StringBuilder(word).reverse().toString();
    }
}

참고: https://mishuni.tistory.com/46, https://girawhale.tistory.com/110