[Algorithm] 프로그래머스 - 가사 검색

https://school.programmers.co.kr/learn/courses/30/lessons/60060

접근

이 문제를 보자마자 딱 들었던 생각이 Trie 자료구조를 사용해야겠다는 것이었다.

마침 얼마 전 Trie 자료구조를 알게 된 문제가 있어 관련 포스팅을 작성했었다.

Trie 자료구조에 대해 궁금하면 다음 글을 읽어보면 도움이 될 것이다.

[Algorithm] 프로그래머스 - [3차] 자동완성

words와 queries 배열의 길이 제한사항이 $2\leq{…}\leq{100,000 }$ 이기 때문에 완전 탐색으로는 이 문제를 풀 수 없다.

그래서 words를 Trie 자료구조상 트리 형태로 저장시키고, queries 배열의 원소들을 Trie에서 하나씩 순차적으로 탐색해야 한다. 트리 자료구조에서 탐색에 드는 시간복잡도는 $O(\log{N})$이다.

물론, 내가 직접 구현한 Trie 자료구조는 일반적인 형태의 트리가 아니므로, 시간복잡도 $O(\log{N})$이 아니다.

자식 노드 TrieNode의 여러 자식을 child라는 Map 멤버 변수로 가지므로,

탐색에 드는 시간복잡도는 $O(\log{N}\log{M})$일 것이다. 이는 Map 자료구조의 탐색에 드는 평균 시간복잡도가 $O(\log{N})$이기 때문이다.

queries 배열의 제한사항을 살펴보면, query는 ‘?’이 시작 구간에만 있거나, 끝 구간에만 있거나, 모두 채워지는 단 세가지 경우만 허용한다.

‘?’이 시작 구간에 있는 경우는 나머지 두 경우보다 처리하기가 까다로울 거 같았다.

이는 내가 Trie 자료구조를 사용하는 것과 관련이 있다.

시작 구간의 ‘?’ 행렬에서 어느 노드로 이동해야 할 지 특정할 수 없었기 때문이다.

마지막 구간의 ‘?’ 행렬은 남은 자식 노드의 갯수를 세어버리면 그만이다.

하지만, 시작 구간에서는 ‘어느 노드’에서의 남은 자식 노드의 갯수를 세어야 하는데, 이 ‘어느 노드’를 참조하는 게 쉽지 않을 뿐더러, 효율적이지 않다.

그래서 ‘?’으로 시작하는 경우는 Trie의 있는 노드와 query 자체를 뒤집어 접근하도록 구현했다.

이러면 하나의 탐색 함수에서 다른 경우를 처리할 수 있다.

소스코드(Java)

import java.util.*;

class TrieNode {
    String key;
    int cnt;
    boolean end;
    Map<String, TrieNode> child;

    TrieNode(String key) {
        this();
        this.key = key;
    }

    TrieNode() {
        child = new HashMap<>();
    }
}

class Trie {
    TrieNode head;

    Trie() {
        this.head = new TrieNode();
    }

    public void insertTree(String[] string) {
        TrieNode cur = head;
        for(String token : string) {
            if(!cur.child.containsKey(token)) {
                cur.child.put(token, new TrieNode(token));
            }
            cur = cur.child.get(token);
            cur.cnt += 1;
        }
        cur.end = true;
    }

    public int searchTree(String[] string) {

        int cnt = 0;
        TrieNode cur = head;
        for(String token : string) {
            cnt += 1;
            if(token.equals("?")) break;
            if(cur.child.containsKey(token)) {
                cur = cur.child.get(token);
            } else {
                return 0;
            }
        }

        if(string.length >= cnt) {
            return remainedElementsCount(cur.child, string.length - cnt);
        } else {
            return 0;
        }
    }

    private int remainedElementsCount(Map<String, TrieNode> child, int depth) {
        if(depth < 0) return 0;
        int count = 0;
        for(String key : child.keySet()) {
            if(depth == 0 && child.get(key).end) {
                count += 1;
            } else {
                count += remainedElementsCount(child.get(key).child, depth-1);
            }
        }
        return count;
    }

}

class Solution {

    public String reversed(String str) {
        return new StringBuilder(str).reverse().toString();
    }

    public int[] solution(String[] words, String[] queries) {


        Trie wordTree = new Trie();
        Trie wordTreeReversed = new Trie();

        for(String word : words) {
            wordTree.insertTree(word.split(""));
            wordTreeReversed.insertTree(reversed(word).split(""));
        }

        int[] result = new int[queries.length];
        int i = 0;

        for(String query : queries) {
            if(query.startsWith("?")) {
                result[i++] = wordTreeReversed.searchTree(reversed(query).split(""));
            } else {
                result[i++] = wordTree.searchTree(query.split(""));
            }
        }

        return result;
    }
}

 

순차적 배열 words를 가지는 wordTree와 그 역순 배열을 가지는 wordTreeReversed가 있다.

탐색을 진행할 때 ‘?’로 시작하지 않으면, 순차적 문자열 query를 탐색하고, 시작하면 그 역순 문자열을 탐색한다.

‘?’ 행렬 구간까지 탐색을 진행하고 그 이후부터는 remainedElementsCount() 재귀 함수를 이용하여 남은 노드의 갯수를 탐색한다. 하지만, 이 때는 몰랐다. 이 추가적인 탐색이 결과에 영향을 줄 것이라는 것을…

탐색 중에는 TrieNode에 boolean 멤버 변수 end를 선언하여, 기존 노드가 끝에 있는 노드인지 아닌지를 구분하여 탐색을 마무리한다.

효율성 테스트 실패

 

올바른 접근

채점을 하고 나니, 실패 원인이 대충 생각이 났다.

아까 잠시 언급했던 재귀함수를 이용한 완전 탐색이었는데,

완전 탐색을 피하려 Trie 자료구조를 사용한건데, 구현하는 과정에서 그 의도를 잊어 다시 원점으로 돌아오는 실수를 했다.
더 이상 탐색으로 이 문제를 접근하는 것은 쉽지 않다. Trie에 노드 삽입 시 노드마다 값을 memoization하는 다이나믹 프로그래밍 방식으로 접근했다.

소스코드(Java)

import java.util.*;

class TrieNode {

    String key;
    Map<Integer, Integer> remainedLengths;
    Map<String, TrieNode> child;

    TrieNode(String key) {
        this();
        this.key = key;
    }

    TrieNode() {
        child = new HashMap<>();
        remainedLengths = new HashMap<>();
    }
}

class Trie {

    TrieNode head;

    Trie() {
        this.head = new TrieNode();
    }

    public void insertTree(String[] string) {

        TrieNode cur = head;
        int idx = 0;

        cur.remainedLengths.put(string.length, cur.remainedLengths.getOrDefault(string.length, 0) + 1);

        for(String token : string) {

            if(!cur.child.containsKey(token)) {
                cur.child.put(token, new TrieNode(token));
            }

            cur = cur.child.get(token);
            idx += 1;
            cur.remainedLengths.put(string.length - idx, cur.remainedLengths.getOrDefault(string.length - idx, 0) + 1);
        }
    }

    public int searchTree(String[] string) {

        TrieNode cur = head;

        int idx = 0;

        for(String token : string) {

            if(token.equals("?")) break;

            idx += 1;

            if(cur.child.containsKey(token)) {
                cur = cur.child.get(token);
            } else {
                return 0;
            }
        }

        if(string.length >= idx) {
            return cur.remainedLengths.getOrDefault(string.length - idx, 0);
        } else {
            return 0;
        }
    }

}

class Solution {

    public String reversed(String str) {
        return new StringBuilder(str).reverse().toString();
    }

    public int[] solution(String[] words, String[] queries) {


        Trie wordTree = new Trie();
        Trie wordTreeReversed = new Trie();

        for(String word : words) {
            wordTree.insertTree(word.split(""));
            wordTreeReversed.insertTree(reversed(word).split(""));
        }

        int[] result = new int[queries.length];
        int i = 0;

        for(String query : queries) {
            if(query.startsWith("?")) {
                result[i++] = wordTreeReversed.searchTree(reversed(query).split(""));
            } else {
                result[i++] = wordTree.searchTree(query.split(""));
            }
        }

        return result;
    }
}

 

나는 삽입하려는 해당 노드에서 주어진 word의 남은 길이를 계수하는 방법을 선택했다.

이를 위해 Trie에 Map 멤버 변수 remainedLengths를 선언했다.

이는 방문하는 각 노드에서 탐색하려는 query의 남은 길이를 키로 받아 그 길이까지의 word의 갯수를 값으로 반환한다.

이러면 추가적인 탐색을 하지 않아도 문제를 해결할 수 있다.

효율성 테스트 성공