[프로그래머스/JAVA] 17685번 [3차] 자동완성 (Trie)

문제

문제 링크

 

2018 KAKAO BLIND RECRUITMENT [3차] 자동완성

https://school.programmers.co.kr/learn/courses/30/lessons/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

 

입출력 예시

words	result
["go","gone","guild"]	7
["abc","def","ghi","jklm"]	4
["word","war","warrior","world"]	15

 

 

문제 풀이

 

접근 방법

• Map<String, Integer> 맵을 활용해서 학습 단어의 단어를 모두 넣는다.
  • 예를 들어 "gone" 이라면 "g", "go", "gon", "gone" 를 추가한다. 문자열을 넣으면서 중복이 있으면 count+1
• 입력받은 단어를 문자 단위로 끊어서 map 을 탐색해서 count 가 1개면 유일하므로 자동완성 시킨다.

 

• 위 풀이로 테스트를 돌려보면 통과는 되지만 몇몇 테스트에서 메모리 초과 실패가 뜬다.
• 그래서 자동완성 관련 알고리즘을 찾아보니 Trie 자료구조가 있었다.
• Trie 자료구조는 트리 형태의 char 를 저장하는 형식이다.

2번 예제 Trie 구조

 

• 우리에겐 유일한 단어이면 자동완성이 된다. 따라서 Trie 노드에 Map 사용해서 count 를 세어준다.
• Trie에 단어를 삽입할때는 단어를 char 단위로 끊어서 저장하고 중복으로 저장된다면 count를 증가시킨다.
• 입력 문자를 입력하면서 count가 1이 될때 자동완성이 된다.

 

코드

Trie 사용 코드

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

public class P_17685 {

    private static int solution(String[] words) {

        Trie trie = new Trie();

        // 모든 단어 삽입
        for (String word : words) {
            trie.insert(word);
        }

        // 입력 문자 수 계산
        int result = 0;
        for (String word : words) {
            result += trie.getMinInputCount(word);
        }

        return result;
    }

    static class TrieNode {
        Map<Character, TrieNode> children;
        int count;

        TrieNode() {
            children = new HashMap<>();
            count = 0;
        }
    }

    static class Trie {
        private TrieNode root;

        Trie() {
            root = new TrieNode();
        }

        // 단어 삽입
        void insert(String word) {
            TrieNode current = root;
            for (char c : word.toCharArray()) {
                current.children.putIfAbsent(c, new TrieNode());
                current = current.children.get(c);
                current.count++;
            }
        }

        // 단어를 탐색하며 입력 문자 수 계산
        int getMinInputCount(String word) {
            TrieNode current = root;
            int inputCount = 0;

            for (char c : word.toCharArray()) {
                inputCount++;
                current = current.children.get(c);

                // 고유한 접두사 발견하면 중단
                if (current.count == 1) {
                    break;
                }
            }

            return inputCount;
        }
    }
}

 

이전 코드

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

public class P_17685 {

    private static int solution(String[] words) {

        // 앞글자의 공통된 부분을 찾아야한다.
        Map<String, Integer> dict = new HashMap<>();

        StringBuilder prefix = new StringBuilder();

        for (String word : words) {

            prefix = new StringBuilder();

            // world 일 경우에는 "w" "wo" "wor" "worl" "world" 를 dict 에 넣는다.
            // "str", 기존 cnt(default 0)+1
            for (int i=0; i<word.length(); i++) {
                prefix.append(word.charAt(i));
                dict.put(prefix.toString(), dict.getOrDefault(prefix.toString(), 0) + 1);
            }
        }

        int result = 0;

        // 단어 돌기
        for (String word : words) {

            // word 추가
            StringBuilder findStr = new StringBuilder();

            // 글자 입력수
            int inputCount = 0;

            for (int i=0; i< word.length(); i++) {
                findStr.append(word.charAt(i));
                inputCount++;

                // findStr 접두사가 1개라면 inputCount 만큼 입력하면 자동완성
                if (dict.get(findStr.toString())==1) {
                    break;
                }
            }

            result += inputCount;

        }

        return result;
    }
}