2018 KAKAO BLIND RECRUITMENT : 자동완성

자동완성

포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, 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

---

Trie 자료구조를 활용한 문제이다.

 

위 문제에 대한 접근 방법에 대해 생각해보도록 하면 다음과 같다.

파라메터로 받은 단어들에 대한 학습에 대한 작업을 진행하고 학습한 단어들을 기반으로 몇 글자를 입력해야 되는지를 판단하는 작업을 진행해야 한다.

즉, 구현해야 할 작업은 총 2가지다.

 

1. 파라메터로 받은 vector<string> words 를 기반으로 각 단어들에 대한 학습을 진행시키도록 한다.

예를 들어서 학습해야 할 단어들 ["go", "gone", "guild"] 이 있다고 하자.

이를 Trie 자료구조를 활용하여 "go", "gone", "guild" 를 학습시킬 경우 다음과 같게 된다.

 

 

이때 ( ) 안에 적혀진 숫자는 학습해온 단어들을 기반으로 한 각 문자의 누적 횟수를 의미한다.

즉, 다음 문자로 이동하면서 체크해줘야 할 것은 해당 문자에 몇 번 방문했는지에 대한 정보가 필요하다.

 

2. 학습한 정보들을 기반으로 하여 각 단어들에 대해서 해당 단어는 몇 글자를 입력해야 하는지를 확인해야 한다.

(1) 예를 들어서 "go" 인 경우를 살펴보도록 한다.

문제에서 주어진 조건 중, "학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다" 라는 조건이 주어졌다.

따라서 "go" 는 "go" 그대로 입력을 해야 하므로 2 글자를 입력해야 한다.

여기서 알 수 있는 점은 적어도 2번 이상 해당 문자에 방문하게 된 경우 그 다음 문자로 이동함과 동시에 입력 해야 할 횟수를 증가시켜야 하는 것을 짐작할 수 있다.

 

(2) 예를 들어서 "guild" 인 경우를 살펴보도록 한다.

 

이번엔 'u' 까지 타이핑을 한 후에 "guild" 라는 단어를 자동 완성을 시켜줄 것으로 보인다.

즉, 단어 중에 문자("guild"의 'u' 혹은 "gone"의 'n')가 단 한번 학습이 되어진 경우 다음 문자로 이동하지 않고 현재까지 타이핑한 문자의 횟수가 답이라는 것을 짐작할 수 있다.

 

※ 주의 사항 : 재귀적 호출을 이용한 Trie 구현은 시간초과가 일어난다.

     이를 해결하기 위해서 loop 문을 이용하여 구현해야 시간초과 없이 통과하는 것으로 보인다.

 

 

Solution Code

 

#include <string>
#include <vector>
#include <malloc.h>

using namespace std;

struct Trie* getTrie();

struct Trie{
    Trie *next[26];
    int check;
    
    void clear() {
        check = 0;
        for(int i=0; i<26; i++)
            next[i] = NULL;
    }
};

Trie* getTrie(){
    Trie* ret;
    ret = (Trie*)malloc(sizeof(Trie));
    ret->clear();
    return ret;
}

Trie* root;

int solution(vector<string> words) {
    int answer = 0;
    Trie* tmp;
    
    root = getTrie();
    
    for(int i=0; i<words.size(); i++) {
        tmp = root;
        string S = words[i];
        int S_size = S.size();
        for(int j=0; j<S_size; j++){
            int c = S[j] - 'a';
            if(tmp->next[c] == NULL) {
                tmp->next[c] = getTrie();
            }
            tmp->next[c]->check++;
            tmp = tmp->next[c];
        }
    }
    
    for(int i=0; i<words.size(); i++) {
        tmp = root;
        string S = words[i];
        int S_size = S.size();
        for(int j=0; j<S_size; j++){
            int c = S[j] - 'a';
            if(tmp->next[c]->check == 1){
                answer += j + 1;
                break;
            }
            tmp = tmp->next[c];
            if(j == S.size() - 1)
                answer += S_size;
        }
    }
    
    return answer;
}