프로그래머스[Lv.4] - [3차] 자동완성

 

 

문제 설명

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

 

---

 

 

 

 

 

 

풀이

예전 코테에서 비슷한 유형의 문제를 푼 기억이 있다.

그때는 dfs로 풀었는데 시간초과가 났던 것 같다.

그래서 그때 이런 유형은 어떻게 풀어야 하는지 찾아봤는데 트라이라는 것을 알게 되었다.

그래서 이번 문제를 보자마자 트라이로 풀면 되겠다고 생각했다.

트라이란 트리 구조를 통해 문자열 검색을 빠른 시간 안에 가능하게 해주는 자료구조이다.

하나의 노드에는 하나의 문자가 들어가고 그 다음에 오는 문자열을 자식으로 갖는다고 생각하면 된다.

예를 들어, gone이라는 문자열과 guild라는 문자열을 트라이를 통해 저장한다고 가정해 보자.

그러면 다음과 같은 구조로 저장이 된다.

자동완성같은 기능을 구현하는 문제에서 많이 사용되는 것 같다.

그 이유는 조회에 장점이 있기 때문이다.

모든 문자열을 비교하여 일치 여부를 판단하는 것보다 문자를 하나씩 따라가 일치 여부를 판단하면 되기 때문이다.

 

 

트라이를 통해 문제를 해결하는 방법은 다음과 같다.

우선, 트라이에 모든 문자열을 저장한다.

이때, 각 문자가 몇 개의 문자열에 포함되어 있는지 카운트해야 한다.

만약, 1개만 포함되어 있다면 그 문자 이후에 문자열 역시 단 한 번만 나온 문자이기 때문에 더 이상 조회하지 않아도 되기 때문이다.

 

문자열을 모두 저장했다면 모든 문자열을 유일한 문자열로 식별이 가능할 때까지 조회를 진행하면 된다.

앞서 말했듯이 해당 노드에 있는 문자가 전체 문자열에서 몇 번 등장했는지 카운팅 했기 때문에 그 문자가 1이거나 뒤에 문자가 더 없다면 탐색을 종료한다.

그렇지 않다면 depth를 하나씩 늘리며 다음 문자에 대한 탐색을 진행하면 된다.

---

 

 

 

 

 

전체 코드

#include <string>
#include <vector>
#include <map>
#include <string.h>
#include <iostream>

using namespace std;

struct Trie {
    bool bFinish; 
    Trie* Node[26];
    int childNum;

    Trie() : bFinish(false), childNum(0) {
        for(int i = 0 ; i < 26; i++) Node[i] = nullptr;
    }

    void insert(const char* Str) {
        childNum++;
        if(*Str == NULL)
        {
            bFinish = true;
            return;
        }
        
        int Cur = *Str - 'a';
        if(Node[Cur] == NULL) Node[Cur] = new Trie();
        
        Node[Cur]->insert(Str + 1);
    }

    int find(const char* key, int depth) {
        if(childNum == 1 || *key == NULL) return depth;
        
        int current = *key - 'a';
        return Node[current]->find(key+1, depth+1);
    }
};

int solution(vector<string> words) {
    int answer = 0;
    
    Trie* Root = new Trie();
    
    for(auto word : words)
    {
        const char *c = word.c_str();
        Root->insert(c);
    }
    
    for(auto word : words)
    {
        const char *c = word.c_str();
        int temp = Root->find(c, 0);
        answer += temp;
    }
    
    
    return answer;
}

---