프로그래머스 문제 - 자동완성

프로그래머스 자동완성 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

N개의 중복 없는 L길이의 단어들이 주어집니다.
주어진 단어들은 학습이 되어 문자열이 입력되면 알맞는 자동완성을 보여줍니다.
단 입력된 문자열과 같은 앞부분이 여러 개 있을 경우 한 가지가 남을 때까지 입력을 해야 한다.
학습된 단어들을 찾을 때 몇 글자를 입력해야 하는 값을 모두 더한 값을 구해야한다.

문자열의 앞 부분을 빠르게 비교하는 것이 중요해보입니다.

문제 풀이

앞부분의 문자열을 차례대로 하나씩 보면서 중첩되는 여러 문자열들을 찾아야합니다.
N <= 100000, L <= 1000000이기에 하나씩 전체를 for문으로 돌려보는 것은 Time Limited가 뜰 것이니 다른 방법을 사용해야 합니다.

사전순으로 단어들을 정리한 후 조금씩만 비교해보는 방법도 있지만, 문자열 검색에 최적인 트라이(Trie) 자료구조를 사용해보았습니다.
트라이는 트리 형태를 띄고 있으며 상위 문자가 하위 문자들의 부모 노드가 되도록 제작됩니다.

단어들을 저장할 Node클래스를 만들어줍니다.
아래로 완성된 단어들의 수를 카운트해줌으로써 만들어진 단어가 한가지가 남았을 경우를 빠르게 찾아줍니다.

class Node
{
    public:
        Node* child[26] = {NULL,};
        bool isWord = false;
        int wordCount[26] = {0,};
};

Node root;

그리고 Node를 사용하여 string에 담긴 단어들을 저장할 insert함수를 만들어줍니다.
string의 담긴 단어들을 찾는 find함수도 만들어주는데, 찾는 도중 완성된 단어가 한가지만 남았을 경우 현재까지 입력된 글자 수를 리턴시켜준다.

void insert(string s)
{
    Node* cur = &root;
    for(int i = 0; i < s.size(); i++)
    {
        if(cur->child[s[i] - 'a'] != NULL)
        {
            cur->wordCount[s[i] - 'a']++;
            cur = cur->child[s[i] - 'a'];
        }
        else
        {
            cur->wordCount[s[i] - 'a']++;
            cur->child[s[i] - 'a'] = new Node;
            cur = cur->child[s[i] - 'a'];
            
        }
    }
    cur->isWord = true;
}

int find(string s)
{
    Node* cur = &root;
    int count = 0;
    for(int i = 0; i < s.size(); i++)
    {
        count++;
        if(cur->wordCount[s[i] - 'a'] == 1)
        {
            return count;
        }
        cur = cur->child[s[i] - 'a'];
    }
    return count;
}

전체 코드

이번 문제는 문자열을 어떻게 검색하는지 여러 방법을 익히는 문제였습니다.
이번에는 트라이 자료구조를 사용하여 문제를 해결하였습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

class Node
{
    public:
        Node* child[26] = {NULL,};
        bool isWord = false;
        int wordCount[26] = {0,};
};

Node root;

void insert(string s)
{
    Node* cur = &root;
    for(int i = 0; i < s.size(); i++)
    {
        if(cur->child[s[i] - 'a'] != NULL)
        {
            cur->wordCount[s[i] - 'a']++;
            cur = cur->child[s[i] - 'a'];
        }
        else
        {
            cur->wordCount[s[i] - 'a']++;
            cur->child[s[i] - 'a'] = new Node;
            cur = cur->child[s[i] - 'a'];
            
        }
    }
    cur->isWord = true;
}

int find(string s)
{
    Node* cur = &root;
    int count = 0;
    for(int i = 0; i < s.size(); i++)
    {
        count++;
        if(cur->wordCount[s[i] - 'a'] == 1)
        {
            return count;
        }
        cur = cur->child[s[i] - 'a'];
    }
    return count;
}

int solution(vector<string> words) {
    int answer = 0;
    for(string s : words)
    {
        insert(s);
    }
    
    for(string s : words)
    {
        answer += find(s);
    }
    
    return answer;
}

출저

https://school.programmers.co.kr/learn/courses/30/lessons/17685