[프로그래머스] 17685_[3차] 자동완성 JAVA

17685_자동완성

문제 설명

포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다! 단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다.
효과가 얼마나 좋을지 알고 싶은 라이언은 학습된 단어들을 찾을 때 몇 글자를 입력해야 하는지 궁금해졌다.

예를 들어, 학습된 단어들이 아래와 같을 때

go
gone
guild

• go를 찾을 때 go를 모두 입력해야 한다.
• gone을 찾을 때 gon 까지 입력해야 한다. (gon이 입력되기 전까지는 go 인지 gone인지 확신할 수 없다.)
• guild를 찾을 때는 gu 까지만 입력하면 guild가 완성된다.
  이 경우 총 입력해야 할 문자의 수는 7이다.

라이언을 도와 위와 같이 문자열이 입력으로 주어지면 학습을 시킨 후, 학습된 단어들을 순서대로 찾을 때 몇 개의 문자를 입력하면 되는지 계산하는 프로그램을 만들어보자.

---

제한 사항

학습과 검색에 사용될 중복 없는 단어 N개가 주어진다.
모든 단어는 알파벳 소문자로 구성되며 단어의 수 N과 단어들의 길이의 총합 L의 범위는 다음과 같다.

• 2 <= N <= 100,000
• 2 <= L <= 1,000,000

---

입출력 예 (설명은 생략)

---

소스코드

import java.util.HashMap;

public class Solution {
    static Node root = new Node();
    public int solution(String[] words) {
        int answer = 0;

        for (String word : words) {
            insert(word);
        }

        answer = cal(root, 0);
        return answer;
    }

    static int cal(Node root, int depth) {
        if (root.maxDepth == 1) {
            return depth;
        }
        int cnt = 0;

        for (char key : root.childNode.keySet()) {
            if (key == '-') {
                cnt += depth;
            } else {
                cnt += cal(root.childNode.get(key), depth + 1);
            }
        }

        return cnt;
    }

    static void insert(String word) {
        Node currentNode = root;

        for (char c : word.toCharArray()) {
            Node newRoot = currentNode.put(c);
            currentNode = newRoot;
        }

        currentNode.put('-');
    }

    static class Node {
        private HashMap<Character, Node> childNode = new HashMap<>();
        private int maxDepth = 0;

        Node put(char c) {
            maxDepth++;
            if (!childNode.containsKey(c)) {
                childNode.put(c, new Node());
            }

            return childNode.get(c);
        }
    }
}

---

Comment

• 프로그래머스에서도 난이도 4에 해당하는 아주 어려운 문제였다.
• 전형적인 Trie 문제였지만 Trie에 대한 이해도가 없었고, 이해를 해도 응용을 못하여 결국, 타 개발자들의 답을 참고하였다.
• 🎈Trie, HashMap, 재귀를 사용해 푼 모습이다.

---