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

 

 

프로그래머스 2020 KAKAO BLIND RECRUITMENT 가사 검색 : https://programmers.co.kr/learn/courses/30/lessons/60060

코딩테스트 연습 - 가사 검색 | 프로그래머스

 

 

예전에 못 풀었다가 다시 한번 도전하게 된 2020 카카오 공채의 가사 검색이다.

트라이라는 자료구조를 처음 알게 된 문제다.

 

이 문제를 처음 접했을 때는 단순하게 정규표현식을 사용해서 문제를 풀어야겠다고 생각했다.

하지만 정규표현식으로 풀게 되면 선형 시간으로 비교를 해야 해서 정확성 테스트는 통과하지만 효율성 테스트를 통과하지 못한다.

따라서 도저히 답을 찾지 못해 구글링을 해보았고, 트라이라는 자료구조를 사용해야 된다는 것을 보게 되었다.

트라이는 트리의 한 종류로써, 문자열을 저장하고 검색하는 데 유용한 자료구조이다.

트라이에 대해 자세한 내용은 여기를 참고하도록 하자.

 

문제에서 검색 키워드는 크게 물음표가 앞에 있는 키워드와 뒤에 있는 키워드로 나뉜다.

물음표가 앞에 있는 키워드는 뒤에서부터 검색을 하고, 물음표가 뒤에 있는 키워드는 앞에서부터 검색을 한다.

따라서 트라이에 가사 단어를 저장할 때 앞과 뒤 두 부분으로 나뉘어서 저장을 한다. (front, back)

예를 들어, 검색 키워드가 "fro??"라면 front에서 검색을 하고, "??odo"라면 back에서 검색을 한다.

또한 길이에 따라서 매칭 되는 단어가 있고 없고가 판단되므로,

길이 100001짜리 Trie 배열을 선언하여, 각 길이에 따라 트라이들을 따로 만들어 준다.

 

 

자료구조를 직접 구현해본 게 언젠지 기억도 안 날 정도로 매번 라이브러리만 갖다 썼었는데,

이런 식으로 직접 구현해보니 재미도 있고 많은 것을 배운 것 같다.

난이도가 좀 있는 문제에서는 트라이 자료구조도 제법 나온다고 하니 이번 기회에 확실히 습득해놔야겠다.

 

 

총 걸린 시간 : 3시간 이상

난이도 : ★★★★★

 

코드

import java.util.HashMap;

class Solution {
    public int[] solution(String[] words, String[] queries) {
        Trie[] tries = new Trie[100001];
        for (String word : words) {  
            int len = word.length();
            if (tries[len] == null) tries[len] = new Trie();
            tries[len].insert(word);
        }

        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int len = queries[i].length();
            if (tries[len] == null) answer[i] = 0;
            else answer[i] = tries[len].getCount(queries[i]);
        }
        return answer;
    }
}

class Trie {
    Node front;
    Node back;

    Trie() {
        this.front = new Node();
        this.back = new Node();
    }

    public void insert(String word) {
        insertFront(word);
        insertBack(word);
    }

    private void insertFront(String word) {
        Node node = front;
        for (int i = 0; i < word.length(); i++) {
            node.count++;
            node = node.children.computeIfAbsent(word.charAt(i), c -> new Node());
        }
    }

    private void insertBack(String word) {
        Node node = back;
        for (int i = word.length() - 1; i >= 0; i--) {
            node.count++;
            node = node.children.computeIfAbsent(word.charAt(i), c -> new Node());
        }
    }

    public int getCount(String query) {
        if (query.charAt(0) == '?') return getCountFromBack(query);
        else return getCountFromFront(query);
    }

    private int getCountFromFront(String query) {
        Node node = front;
        for (int i = 0; i < query.length(); i++) {
            if (query.charAt(i) == '?') break;
            if (!node.children.containsKey(query.charAt(i))) return 0;
            node = node.children.get(query.charAt(i));
        }
        return node.count;
    }

    private int getCountFromBack(String query) {
        Node node = back;
        for (int i = query.length() - 1; i >= 0; i--) {
            if (query.charAt(i) == '?') break;
            if (!node.children.containsKey(query.charAt(i))) return 0;
            node = node.children.get(query.charAt(i));
        }
        return node.count;
    }
}

class Node {
    Map<Character, Node> children;
    int count;

    Node(){
        this.children = new HashMap<>();
        this.count = 0;
    }
}