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

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

접근

오늘날 어느 서비스를 사용하더라도 기본적으로 검색에 탑재되어 있는 자동완성을 직접 구현하는 문제이다.

자동완성을 구현할 때 기본적으로 사용하는 자료구조가 따로 있다고 한다. Trie이다.

Trie는 입력된 문자열의 한 문자를 가리키는 노드를 트리 구조의 형태로 가진다.

TrieNode는 key, cnt, child 세 가지 멤버변수를 가진다.

• key
  • 문자를 가리킨다.
• cnt
  • 해당 문자의 수를 가리킨다.
• child
  • 자식 TrieNode를 가리킨다.

이 문제에서 요구하는 바는 단어를 찾을 때 입력해야 할 총 문자수이다.

따라서, cnt의 값이 1이면 한 문자열에서 그 노드까지 방문한 문자의 수만큼이 입력해야 할 문자수를 의미하게 된다.

words에 대해 iteration을 수행하면 문제에서 요구하는 답을 도출할 수 있다.

반대로, cnt의 값이 1보다 큰 경우에는 현재 노드까지의 문자열이 여러 개가 있을 수 있기 때문에 특정 지을 수가 없다.

따라서, 결국에는 cnt가 1인 경우까지 노드를 이동하거나, 입력된 문자열의 끝까지 이동해야 한다.

문자열의 끝까지 노드를 이동했음에도 cnt가 1보다 큰 경우에는 입력된 문자열의 길이가 ‘입력해야 할 문자수’가 된다.

참고로, cnt가 0인 경우는 없다. 입력된 문자열(문제에서는 학습된 단어라고 표현)에 한해서만 ‘찾기’가 수행되기 때문이다.

소스코드(Java)

import java.util.*;

class TrieNode {
    String key;
    int cnt;
    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;
        }
    }

    public int searchTree(String[] string) {
        TrieNode cur = head;
        int cnt = 0;
        for(String token : string) {
            cnt += 1;
            cur = cur.child.get(token);
            if(cur.cnt == 1) {
                return cnt;
            }
        }
        return string.length;
    }
}

class Solution {
    public int solution(String[] words) {
        int answer = 0;
        Trie wordTree = new Trie();
        for (String word : words) {
            wordTree.insertTree(word.split(""));
        }
        for(String word : words) {
            answer += wordTree.searchTree(word.split(""));
        }
        return answer;
    }
}