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

문제

---

포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, 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	return
["go","gone","guild"]	7
["abc","def","ghi","jklm"]	4
["word","war","warrior","world"]	15

입출력 설명

• 첫 번째 예제는 본문 설명과 같다.
• 두 번째 예제에서는 모든 단어들이 공통된 부분이 없으므로, 가장 앞글자만 입력하면 된다.
• 세 번째 예제는 총 15 자를 입력해야 하고 설명은 아래와 같다.
  • word는 word모두 입력해야 한다.
  • war는 war 까지 모두 입력해야 한다.
  • warrior는 warr 까지만 입력하면 된다.
  • world는 worl까지 입력해야 한다. (word와 구분되어야 함을 명심하자)

 

 

 

풀이

---

Trie알고리즘을 이용해서 분에를 풀수있다.

 

알고리즘 순서

1. 단어를 Trie 트리에 저장한다.
2. 현재 알파벳까지의 단어개수를 저장한다.
3. 저장된 트리를 이용하여 단어개수가 1이 되면 해당 단어는 자동완성이 가능한 경우가 된다.

 

Trie 트리에 들어가는 노드다.

count를 이용하여 현재 알파벳까지를 포함하는 단어의 갯수를 저장한다.

HashMap을 이용하여 하위 알파벳의 node를 저장하였다.

static class Node{
    int count;
    HashMap<Character, Node> child;

    public Node(){
        this.count = 0;
        this.child = new HashMap<>();
    }
}

 

Trie 트리의 핵심이 되는 부분이다. 

insert 메서드는 dfs 방식으로 해당 알파벳의 node로 들어가며 count++을 해주어 단어갯수를 표시해준다.

getCount 메서드는 count == 1 이 될때까지의 횟수를 return 해준다.

static class Trie{

    Node top;

    public Trie(){
        this.top = new Node();
    }

    public void insert(String string){
        Node now = top;

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

            if(!now.child.containsKey(string.charAt(i))){
                now.child.put(string.charAt(i), new Node());   
            }
            now = now.child.get(string.charAt(i));                    
            now.count++;
        }
    }

    public int getCount(String string){
        Node now = top;

        int cnt = 0;
        for(int i = 0 ; i < string.length() ; i++){
            now = now.child.get(string.charAt(i));
            cnt++;

            if(now.count <= 1){
                break;
            }
        }

        return cnt;
    }
}

 

 

 

<전체코드>

import java.util.*;

class Solution {
    
    static class Node{
        int count;
        HashMap<Character, Node> child;

        public Node(){
            this.count = 0;
            this.child = new HashMap<>();
        }
    }
    
    static class Trie{

        Node top;

        public Trie(){
            this.top = new Node();
        }

        public void insert(String string){
            Node now = top;

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

                if(!now.child.containsKey(string.charAt(i))){
                    now.child.put(string.charAt(i), new Node());   
                }
                now = now.child.get(string.charAt(i));                    
                now.count++;
            }
        }

        public int getCount(String string){
            Node now = top;

            int cnt = 0;
            for(int i = 0 ; i < string.length() ; i++){
                now = now.child.get(string.charAt(i));
                cnt++;

                if(now.count <= 1){
                    break;
                }
            }

            return cnt;
        }
    }
    
    
    public int solution(String[] words) {
        int answer = 0;
        
        Trie trie = new Trie();
        for(int i = 0 ; i < words.length ; i++){
            trie.insert(words[i]);
        }
        
        for(int i = 0 ; i < words.length ; i++){

            answer += trie.getCount(words[i]);
        }
        
        return answer;
    }
}