[프로그래머스] 17685. 자동완성

문제 링크

[프로그래머스] 17685. 자동완성

풀이 과정

자료구조

트라이(Trie)

트라이 자료구조를 활용해서 문제를 해결할 수 있었습니다. 일반적인 트라이에 추가로, 문자열을 삽입할 때마다, 문자열을 구성하는 각 문자들의 사용 횟수(카운트)를 증가시켜 저장해 두었습니다. 노드의 카운트 변수가 1일 때에는, 더이상의 탐색이 불필요하므로(= 이후 탐색을 통해 만들어지는 문자열이 유일하므로), 탐색을 더이상 진행하지 않아도 됐습니다. 이 부분이 문제가 요구하는 자동완성 기능이 됩니다.

insert(“go”); insert(“gone”);

예를 들어, 위와 같이 go 와 gone 을 삽입하게 되면, 아래 사진과 같이 트라이는 각 알파벳이 몇 번 사용되었는지 체크하게 됩니다.

트라이 탐색

트라이 자료구조 탐색은 다음과 같이 이뤄집니다.

탐색할 문자열을 입력받아, 문자 각각을 순회하면서, 현재 문자를 부모로 두고, 자식 노드인 다음 문자를 계속해서 탐색해 나아갑니다. 이후, 마지막 문자에 해당하는 노드에 도달하면, 해당 문자가 문자열의 마지막 문자인지를 검사하는 불리언 변수( isTerminal )의 값에 따라 탐색 결과를 결정지으며 종료하게 됩니다.

입력 예시

[“go”, “gone”, “guild”]

문제의 입력 예시를 트라이 구조로 구성하면 아래와 같습니다.

검색 문자열 각 문자를 노드로 삼아 트리를 탐색하게 됩니다. 이 문제는, 트라이가 갖는 각 노드가 종단인지를 판별하는 isTerminal 변수와 각 문자의 사용 횟수를 저장하는 cnt 변수를 이용해 문제를 쉽게 해결할 수 있습니다. 해당 노드의 cnt 변수 값이 1인 경우, 아래로 탐색을 계속해 만들어 지는 문자열이 유일하기 때문에 탐색을 멈출 수 있습니다.

탐색 문자열 go 를 트라이에서 탐색하게 되면, g → o 로 탐색 문자열의 모든 문자를 탐색하게 되고, 따라서 마지막 문자까지 순회가 끝나야 go 가 유일해집니다. 마지막 문자인지는 앞서 말한 isTerminal 멤버 변수를 통해 확인할 수 있습니다. 그러므로, 입력해야 되는 문자의 수는 2가 됩니다.

탐색 문자열 gone 을 트라이에서 탐색하게 되면, g → o → n 까지 탐색하는 순간, 문자열이 유일해집니다(=식별 가능해집니다). 다시 말해, 알파벳 n을 갖는 노드의 cnt 값이 1이므로, 여기서 탐색을 멈출 수 있게 됩니다. 그러므로, 입력해야 되는 문자의 수는 3이 됩니다.


탐색 문자열 guild 를 트라이에서 탐색하게 되면, g → u 까지 탐색하는 순간, 문자열이 유일해집니다. 다시 말해, 알파벳 u를 갖는 노드의 cnt 값이 1이므로, 여기서 탐색을 멈출 수 있게 됩니다. 그러므로, 입력해야 되는 문자의 수는 2가 됩니다.

코드

public class Main {
    public static int solution(String[] words) {
        Trie trie = new Trie();
        int answer = 0;

        for (String word : words)
            trie.insert(word);

        for (String word : words)
            answer += trie.find(word);

        System.out.println(answer);

        return answer;
    }

    public static int ctoi(char ch) {
        return ch - 'a';
    }

    public static class Trie {
        TrieNode root;

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

        public void insert(String str) {
            TrieNode current = root;

            for (int i = 0; i < str.length(); i++) {
                char ch = str.charAt(i);
                int idx = ctoi(ch);

                if (current.children[idx] == null) {
                    current.children[idx] = new TrieNode();
                }

                current.children[idx].value = ch;
                current.children[idx].cnt++;

                current = current.children[idx];
            }

            current.isTerminal = true;
        }

        public int find(String str) {
            TrieNode current = this.root;
            int cnt = 0;

            for (int i = 0; i < str.length(); i++) {
                cnt++;

                char ch = str.charAt(i);
                int idx = ctoi(ch);

                if (current.children[idx].cnt == 1) return cnt;

                current = current.children[idx];
            }

            if (current != null && current.isTerminal)
                return cnt;

            else return -1;
        }
    }

    public static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        int cnt = 0;
        boolean isTerminal = false;
        char value;
    }

    public static void main(String[] args) {
        solution(new String[]{"go", "gone", "guild"});
//        solution(new String[]{"abc", "def", "ghi", "jklm"});
//        solution(new String[]{"word", "war", "warrior", "world"});
    }
}