20210608

목표

• Trie 알고리즘 공부
• 최적화 문제 푸는법(코딩 인터뷰 완전 분석) 정리

Facts

전화번호 목록 알고리즘 문제 풀이

Feelings

힘이 되는 사람이 되고 싶다.

Findings

트라이(Trie) 알고리즘을 학습했다.
프로그래머스의 문제중 전화번호 목록 문제를 최적화하는 방법이 해시를 이용하는 방법과 트라이를 이용하는 방법 두가지라서 먼저 해시로 해결한다음, 트라이로 해결하기 위해 학습하게 되었다.

깊이있게 학습할 시간이 부족해서 일단 대략적인 개념과 구현에 초점을 맞추었다. 목표를 트라이 자료구조의 인터페이스를 이해하고 구현하자 였다. 마침 리트코드에 딱 트라이 구현을 테스트할 수 있는 문제가 바로 있어서 유용하게 써먹었다. https://leetcode.com/problems/implement-trie-prefix-tree/

졸린 상태로 짜서 구현이 형편없다. 다시 도전하자.

public class Trie implements TrieInterface {
    TrieNode root;

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

    public boolean search(String word) {
        var currentNode = this.root;
        for (Character letter : word.toCharArray()) {
            if (!currentNode.children.containsKey(letter)) {
                return false;
            }
            currentNode = currentNode.children.get(letter);
        }

        return currentNode.ended;
    }

    public void insert(String word) {
        var currentNode = this.root;
        for (Character letter : word.toCharArray()) {
            if (currentNode.children.containsKey(letter)) {
                currentNode = currentNode.children.get(letter);
                continue;
            }
            var childNode = new TrieNode(letter);
            currentNode.children.put(letter, childNode);
            currentNode = childNode;
        }
        currentNode.end();
    }

    public boolean startsWith(String prefix) {
        var currentNode = this.root;
        for (Character letter : prefix.toCharArray()) {
            if (!currentNode.children.containsKey(letter)) {
                return false;
            }
            currentNode = currentNode.children.get(letter);
        }

        return true;
    }
}