자동완성

자동완성

포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다! 단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다.
효과가 얼마나 좋을지 알고 싶은 라이언은 학습된 단어들을 찾을 때 몇 글자를 입력해야 하는지 궁금해졌다.
라이언을 도와 위와 같이 문자열이 입력으로 주어지면 학습을 시킨 후, 학습된 단어들을 순서대로 찾을 때 몇 개의 문자를 입력하면 되는지 계산하는 프로그램을 만들어보자.

입력 형식

학습과 검색에 사용될 중복 없는 단어 N개가 주어진다.
모든 단어는 알파벳 소문자로 구성되며 단어의 수 N과 단어들의 길이의 총합 L의 범위는 다음과 같다.
2 <= N <= 100,000
2 <= L <= 1,000,000

맨처음에는 정규식을 통해 String 비교를 생각했으나 단어의 수가 10만개이기에 모든 단어를 비교하기에는 문제가 있다고 판단 다른 방법을 찾아보았다.

맨 처음 찾은 방식은 트라이 알고리즘이다.
트라이 알고리즘은 일반적인 트리 알고리즘중 하나이며 이진 구조가 아닌 m-way형태의 트리중 하나입니다 <key,value>형태의 맵을 가지고있는 노드를 가지고있으며 key는 하나의 알파벳 value는 해당하는 자식노드입니다.

이를 통해 Trie 알고리즘으로 String을 분해해서 char형태로 도식화 한다면 모든 단어를 비교할 필요없이 하나의 트리로 문제를 해결할수 있다고 생각했다.

코드(Trie 알고리즘)

import java.util.*;
class Solution {
    static Trie node =new Trie();
    public int solution(String[] words) {
        int answer = 0;
          for (String word : words) {
            insert(word);
        }      
          answer =count(node,0);                   
        
        return answer;
    }
    static class Trie{
        private Map<Character,Trie> child;       
        private int count;
        public Trie(){
            this.child = new HashMap<>();
            this.count = 0;
        }
        Map<Character,Trie> getChild(){
            count++;
            return this.child;
        }
    }
    public void insert(String word){
        Trie Node = this.node;

		for (int i = 0; i < word.length(); i++) {
			Node = Node.getChild().computeIfAbsent(word.charAt(i), c -> new Trie());
		}
        Node = Node.getChild().computeIfAbsent('*', c -> new Trie());
    }
    public int count(Trie root,int cnt) {
        if(root.count == 1){
            return cnt;
        }
        int val = 0;
        for(char key: root.child.keySet()){
            if(key == '*'){
                val += cnt;
            }
            else{
                val += count(root.child.get(key), cnt+1);
            }
        }
        return val;
        }
}

다른 방식으로는 정렬만 한다면 앞과 뒤의 단어만 비교해서 값을 찾아낼수있다는것을 알아냈다 이에 경우 최악의 경우 10만 가까이의 처리량만 나타나므로 문제가 되지않는다.

이 경우 중요한점은 포함관계일 경우 문자 전체를 사용하고 아닌경우 +1해주는 방식이 있다는것만 주의하면 문제가 없다.

코드(정렬)

import java.util.*;
class Solution {
    public int solution(String[] words) {
        int answer = 0;
        int[] counts = new int[words.length];
        Arrays.sort(words);
        for(int i=0;i<words.length-1;i++){
            int len = Math.min(words[i].length(), words[i + 1].length());
            int count = sameWordCount(words[i], words[i + 1]);
                      
            if(count == len) {           
                counts[i] =  Math.max(counts[i], count);                      
            }else {          
                counts[i] =  Math.max(counts[i], count + 1);                      
            }           
            counts[i + 1] = Math.max(counts[i + 1], count + 1);            
        }

        for(int count : counts) 
            answer += count;
        
        return answer;
    }
    int sameWordCount(String a,String b){
        int count = 0;
        int len = Math.min(a.length(),b.length());
        for(int i = 0; i < len; i++) {
            if(a.charAt(i) != b.charAt(i)) {
                return count;
            }
            count++;
        }
        return count;
    }
}