프로그래머스 자동완성 (JAVA)

2018 KAKAO BLIND RECRUITMENT > 자동완성

 

---

자동 완성

https://programmers.co.kr/learn/courses/30/lessons/17685

코딩테스트 연습 - [3차] 자동완성

 

 

Trie 알고리즘을 활용하여 풀 수 있는 전형적인 문제이다.

 

개인적으로는 Trie 알고리즘을 활용하여 문제를 풀이할 때 

 

node.children.computeIfAbsent(word.charAt(i), (e) -> new Node());
node = node.children.get(word.charAt(i));

이렇게 다음 depth로 넘어가는 형태의 코드가 깔끔하고 보기 좋다고 생각한다.

 

 

import java.util.*;

class Solution {
    static Trie root = new Trie(new Node());

    public static int solution(String[] words) {
        int answer = 0;
        for (String word : words) {
            root.insert(word);
        }
        for (String word : words) {
            answer += root.count(word);
        }
        return answer;
    }


    static class Trie {

        Node node;

        public Trie(Node node) {
            this.node = node;
        }

        public void insert(String word) {
            Node node = this.node;

            for (int i = 0; i < word.length(); i++) {
                node.children.computeIfAbsent(word.charAt(i), (e) -> new Node());
                node.count++;
                node = node.children.get(word.charAt(i));
            }
            node.children.computeIfAbsent('*', (e) -> new Node());
            node.count++;
        }

        public int count(String word) {
            Node node = this.node;
            int cnt = 0;
            for (int i = 0; i < word.length(); i++) {
                cnt++;
                if (node.children.get(word.charAt(i)).count > 1) {
                    node = node.children.get(word.charAt(i));
                } else {
                    break;
                }
            }
            return cnt;

        }
    }

    static class Node {

        Map<Character, Node> children;
        int count;

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

        }
    }

}