카카오 가사 검색 문제(Trie 트리)

카카오 가사 검색 문제를 풀어 보았습니다. 아래 링크(프로그래머스) 에서 풀어 보실수 있습니다.

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

처음의 다양한 접근 방법을 생각해 봤습니다.

1. word의 길이와 query의 길이가 같은 것들만 순차 탐색으로 찾는 접근

2. word들을 모두 합쳐서 하나의 문자열에서 query의 패턴을 kmp로 찾는 접근

 

하지만, 2가지 방법 모두 실패 하였습니다.

1번 방법은 일반 테스트는 모두 통과하지만, 효율성 테스트에서 실패

2번 방법은 완전히 매칭되는 단어를 찾는 문제이여서, 완전히 접근 방법 부터 틀렸습니다.(문제에서 접두사, 접미사 라는 단어가 나오길래, kmp를 의심;;)

 

다시, 이번엔 구글의 도움을 받아서 시도 했습니다.

1. 길이 별로 단어의 리스트를 담는 2차원 배열을 이용한 이진 탐색 방법

2. 길이 별로 단어의 리스트를 한 글자 씩 Tree(Trie 자료구조)의 담는 이진 탐색 방법

 

먼저, 2번 방법은 1번 방법을 응용해 2차원 배열 대신 Trie 자료구조를 만들어 담는 방법일 뿐, 접근 방법은 비슷 합니다.

따라서, Trie 자료구조를 공부 할겸, 2번 방법으로 구현해 보았습니다.

 

 

구현 순서

1. word의 길이 별로 Trie(트라이) 트리를 만들고 word들을 Trie(트라이) 트리의 insert 해줍니다.

2. query의 길이에 해당하는 Trie(트라이) 트리의 접근해, 해당 query의 갯수를 얻어 옵니다.

3. Trie(트라이) 트리는 접두사의 '?' 가 달리는 경우를 탐색 하기 위해서, front node와 back node를 가지고 있습니다.

4. Trie(트라이) 트리는 접두사의 '?' 가 달리는 query 를 위해서 insertFront(), insertBack() 을 가지고 있습니다.

5. insertBack()은 접두사의 '?' 가 달려있는 query를 조회 하기 위해서 word를 뒤집어서 insert 해줍니다. (예 : 오징어 -> 어징오)

6. Trie(트라이) 트리의 접두사의 '?' 가 달려있는 query의 갯수를 얻기 위해서 getCountFromBack() 메서드를 가지고 있습니다. 

7. 여기서, node는 한 글자를 노드로 치며, children 노드를 가지고 있습니다.

8. node 는 children의 갯수를 담고 있는 count 변수도 가지고 있습니다.

 

 

java 소스 구현

1. word의 길이 별로 Trie(트라이) 트리를 만들고 word들을 Trie(트라이) 트리의 insert 해줍니다.

2. query의 길이에 해당하는 Trie(트라이) 트리의 접근해, 해당 query의 갯수를 얻어 옵니다.

 

public int[] solution(String[] words, String[] queries) {
	// words 의 단어들의 갯수는 100000
        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;
    }

 

 

3. Trie(트라이) 트리는 접두사의 '?' 가 달리는 경우를 탐색 하기 위해서, front node와 back node를 가지고 있습니다.

4. Trie(트라이) 트리는 접두사의 '?' 가 달리는 query 를 위해서 insertFront(), insertBack() 을 가지고 있습니다.

5. insertBack()은 접두사의 '?' 가 달려있는 query를 조회 하기 위해서, word를 뒤집어서 insert 해줍니다. (예 : 오징어 -> 어징오)

6. Trie(트라이) 트리의 접두사의 '?' 가 달려있는 query의 갯수를 얻기 위해서 getCountFromBack() 메서드를 가지고 있습니다. 

 

class Trie{
    Node front; //query 의 접미사의 '?'가 시작되는 경우
    Node back;  //query 의 접두사의 '?'가 시작되는 경우
    // 두 경우를 분리 하는 이유는 접두사의 '?'가 있을 경우 node를 전부 탐색해야 하므로
    // 분리 하여 시간 복잡도를 줄일 수 있다.

    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 = this.front;
        for (int i = 0; i < word.length(); i++) {
            node.count++; // 한글자 단위 씩 count 증가(예: 대(2)한(2)민(1)국(1) | 대(2)한(2)이(1))
            node = node.children.computeIfAbsent(word.charAt(i), c -> new Node());
        }
    }

    private void insertBack(String word){
        Node node = this.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 = this.front;
        for (int i = 0; i < query.length(); i++) {
            if (query.charAt(i) == '?')
                break; //Trie 트리를 만들때 길이별로 만들기 때문에 나머지는 ("???"의 연속), 따라서 해당 node 의 count 만 반환하면 됨.
            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 = this.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;
    }
}

 

  

 

7. 여기서, node는 한 글자를 노드로 치며, children 노드를 가지고 있습니다.

8. node 는 children의 갯수를 담고 있는 count 변수도 가지고 있습니다.

 

// 글자 하나를 표현
class Node{
    Map<Character, Node> children;
    int count; // 자신의 children 의 갯수

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