[프로그래머스][Level4] 자동완성 - JAVA

[문제]

• 2018 KAKAO BLIND RECRUITMENT

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

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

 

[풀이]

단어 검색 관련 문제는 Trie 트리 자료구조를 이용하여 풀어야 한다. 

(단어 검색, 자동 완성 등등 --> 자동으로 "Trie"가 떠올라야함)

 

<Trie자료구조 JAVA 코드>

Trie 구현코드를 처음부터 끝까지 작성하기는 쉽지 않다.

개인적으로 이런 문제를 풀 때는 팀노트나 블로그에 기록해두고 그때 그때 찾아서 응용하는 편이다.

package com.algorithm.tree;

import java.util.HashMap;
import java.util.Map;

public class TrieTree {

    static class TrieNode {
        private Map<Character, TrieNode> childNodes = new HashMap<>();
        private boolean isLastChar;
    }

    static class Trie {
        TrieNode rootNode;

        public Trie() {
            rootNode = new TrieNode();
        }

        void insert(String word) {
            TrieNode thisNode = this.rootNode;

            for (int i = 0; i < word.length(); i++) {
                thisNode = thisNode.childNodes.computeIfAbsent(word.charAt(i), c -> new TrieNode());
            }
            thisNode.isLastChar = true;
        }

        boolean contains(String word) {
            TrieNode thisNode = this.rootNode;

            for (int i = 0; i < word.length(); i++) {
                char character = word.charAt(i);

                TrieNode node = thisNode.childNodes.get(character);

                if (node == null) {
                    return false;
                }

                thisNode = node;
            }
            return thisNode.isLastChar;
        }

        void delete(String word) {
            delete(this.rootNode, word, 0);
        }

        void delete(TrieNode thisNode, String word, int index) {
            char character = word.charAt(index);

            if (!thisNode.childNodes.containsKey(character)) {
                throw new Error("There is no [" + word + "] in this Trie.");
            }

            TrieNode childNode = thisNode.childNodes.get(character);
            index++;

            if (index == word.length()) {
                if (!childNode.isLastChar) {
                    throw new Error("There is no [" + word + "] in this Trie.");
                }
                childNode.isLastChar = false;

                if (childNode.childNodes.isEmpty()) {
                    thisNode.childNodes.remove(character);
                }
            } else {
                delete(childNode, word, index);

                if (!childNode.isLastChar && childNode.childNodes.isEmpty()) {
                    thisNode.childNodes.remove(character);
                }
            }
        }
    }
}

 

<접근 방법>

루트 노드부터 시작하여 자식 노드로 내려가며 문자 하나하나씩을 순차적으로 탐색한다. 

자식노드로 내려가면서 카운팅한다.(문자 입력 개수 카운팅)

이 문자가 현재 검색하려는 단어에만 들어가는지, 이외에 다른 단어에도 들어가는지를 알아내면 된다. 

1. 현재 검색하려는 단어에만 포함되는 문자라면? -> 문자 입력 개수 리턴

2. 현재 검색하려는 단어 이외에 다른 단어들에도 포함된다. -> 자식노드로 더 내려감

 static class TrieNode {
        private Map<Character, TrieNode> childNodes = new HashMap<>();
        private int cnt; // 해당 문자가 몇개의 단어들에 포함되는지 카운트
}

 

 

 

[코드]

package com.algorithm.kakaoTest.three;

import java.util.HashMap;
import java.util.Map;

/**
 * 자동 완성
 * 소요시간: 57분 38초
 */
public class Test03 {
    public static void main(String[] args) {
        String[] words =// {"go", "gone", "guild"};
                //{"word", "war", "warrior", "world"};
                {"abc", "def", "ghi", "jklm"};
        int answer = solution(words);
        System.out.println(answer);
    }

    static class TrieNode {
        private Map<Character, TrieNode> childNodes = new HashMap<>();
        private int cnt;
    }

    static class Trie {
        TrieNode rootNode;

        public Trie() {
            rootNode = new TrieNode();
        }

        void insert(String word) {
            TrieNode thisNode = this.rootNode;

            for (int i = 0; i < word.length(); i++) {
                thisNode = thisNode.childNodes.computeIfAbsent(word.charAt(i), c -> new TrieNode());
                thisNode.cnt++;
            }
        }

        int getInputCounts(String word) {
            int count = 0;
            TrieNode thisNode = this.rootNode;

            for (int i = 0; i < word.length(); i++) {
                char character = word.charAt(i);
                TrieNode node = thisNode.childNodes.get(character);
                count++;

                if (node.cnt == 1) {
                    return count;
                }
                thisNode = node;
            }
            return count;
        }
    }

    public static int solution(String[] words) {
        int answer = 0;

        // Trie 트리 생성
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }

        for (String word : words) {
            answer += trie.getInputCounts(word);
        }
        return answer;
    }
}

 

참고
https://the-dev.tistory.com/2
https://the-dev.tistory.com/3