Algospot SOLONG

문제 링크입니다: https://algospot.com/judge/problem/read/SOLONG

트라이(Trie) 자료구조(=접두사 트리(prefix tree))를 사용하는 문제였습니다.

트라이를 간단하게 설명하자면 아래와 같습니다.

정수나 실수 혹은 문자에 대해서는 BST(이진 탐색 트리)가 시간복잡도 O(logN)으로 훌륭하게 동작합니다.

하지만 문자열에 대해서 BST를 사용한다면 문자열의 최대길이가 M일 경우 시간복잡도가 O(MlogN)이 되기 때문에 생각만큼 효율적이지 않습니다.

트라이는 위와 같은 문제를 메모리를 희생하면서 시간복잡도를 O(M)으로 단축시켜줍니다.

트라이의 중요한 속성은 루트에서 한 노드까지 내려가는 경로에서 만나는 글자들을 모으면 해당 노드에 대응되는 접두사(prefix)를 얻을 수 있다는 점입니다.

따라서 트라이의 한 노드를 표현하는 객체는 자손 노드들을 가리키는 포인터 목록과, 종료노드인지 구분하는 boolean 변수로 구성됩니다.

이 때, 포인터 목록을 동적 배열이 아닌 입력에 등장할 수 있는 모든 문자에 각각 대응되는 원소를 갖는 고정 길이 배열로 구현합니다.(탐색과 입력의 시간 복잡도가 O(M)인 이유)

보다 자세한 설명은 라이님(https://kks227.blog.me/220938122295?Redirect=Log&from=postView)이 잘 설명해주셨기 때문에 참고하시면 많은 도움이 될 것입니다!

트라이에 대한 설명은 이 정도로 마무리하고 SOLONG 문제의 알고리즘은 아래와 같습니다.

1. 메모리 사용량과 계산량을 최소화하기 위해 사전에 주어진 문자열들을 출현빈도의 내림차순으로 정렬하고 출현빈도가 같다면 사전순으로 오름차순 정렬을 합니다.

2. 사전에 있는 모든 문자열을 트라이에 넣습니다.

3. 문자열 사이사이 공백도 문자열에 포함되기 때문에 초기 값을 M - 1로 잡습니다.

4. 해당 문자열에 대해 countKeys 함수를 호출하는데 사전에 등록된 문자열인지 아닌지 판별하여 누르는 횟수를 계산합니다.

5. 4번을 M번 반복하고 3번에서 초기 값으로 잡은 M - 1과 더해줍니다.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

using namespace std;

 

const int ALPHABETS = 26;

 

int toNumber(char ch)

{

        return ch - 'A';

}

 

struct TrieNode

{

        TrieNode *children[ALPHABETS];

        //이 노드에서 종료하는 문자열의 번호, 없으면 -1

        int terminal;

        //이 노드를 루트로 하는 트라이에 가장 먼저 추가된 단어의 번호

        //-1로 초기화

        int first;

        TrieNode() : terminal(-1), first(-1)

        {

                 memset(children, 0, sizeof(children));

        }

        ~TrieNode()

        {

                 for (int i = 0; i < ALPHABETS; i++)

                         if (children[i])

                                 delete children[i];

        }

        //이 노드를 루트로 하는 트라이에 번호 id인 문자열 key를 추가한다

        void insert(const char *key, int id)

        {

                 //first를 우선 갱신

                 if (first == -1)

                         first = id;

                 //문자열이 끝났다면 terminal만 바꾸고 종료

                 if (*key == 0)

                         terminal = id;

                 else

                 {

                         int next = toNumber(*key);

                         //해당 자식 노드가 없다면 생성

                         if (children[next] == NULL)

                                 children[next] = new TrieNode();

                         //해당 자식 노드로 재귀 호출

                         children[next]->insert(key + 1, id);

                 }

        }

        //이 노드를 루트로 하는 트라이에 문자열 key와 대응되는 노드를 찾는다

        //없으면 NULL return

        TrieNode *find(const char *key)

        {

                 if (*key == 0)

                         return this;

                 int next = toNumber(*key);

                 if (children[next] == NULL)

                         return NULL;

                 return children[next]->find(key + 1);

        }

        //이 노드까지 타이핑해 왔을 떄, 번호 id인 key를 타이핑하기 위해

        //최소 몇 번의 키를 눌러야 하나

        int type(const char *key, int id)

        {

                 //문자열 종료시

                 if (*key == 0)

                         return 0;

                 //이 노드에서 추천되는 문자열이 이 문자열이면 탭 누르고 종료

                 if (first == id)

                         return 1;

                 //아니면 다음 문자를 타이핑한다

                 int next = toNumber(*key);

                 return 1 + children[next]->type(key + 1, id);

        }

};

 

//사전을 타나태는 트라이가 주어질 때, 단어 word를 타이핑하는 데

//몇 번이나 키를 눌러야하는지 계산한다

int countKeys(TrieNode *trie, const char *word)

{

        //이 문자열이 사전에 있는지 확인하고, 있다면 번호를 구한다

        TrieNode *node = trie->find(word);

        //사전에 없으면 직접 타이핑할 수 밖에 없다

        if (node == NULL || node->terminal == -1)

                 return strlen(word);

        //탐색하면서 타이핑할 방법을 찾는다

        return trie->type(word, node->terminal);

}

 

//입력에 주어지는 단어들을 정렬해서 트라이로 변환

TrieNode *readInput(int words)

{

        //단어들을 출현 빈도의 내림차순, 단어의 오름차순으로 정렬한다

        vector<pair<int, string>> input;

        for (int i = 0; i < words; i++)

        {

                 char buf[11];

                 int freq;

                 cin >> buf >> freq;

                 input.push_back(make_pair(-freq, buf));

        }

        sort(input.begin(), input.end());

        //이 때 앞에 있는 단어일수록 우선순위가 높다

        //배열의 인덱스를 각 단어의 번호로 쓰자

        TrieNode *trie = new TrieNode();

        for (int i = 0; i < input.size(); i++)

                 trie->insert(input[i].second.c_str(), i);

        trie->first = -1;

        return trie;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        int test_case;

        cin >> test_case;

 

        for (int t = 0; t < test_case; t++)

        {

                 int N, M;

                 cin >> N >> M;

 

                 TrieNode *trie = readInput(N);

                 int result = M - 1; //space bar

                 for (int i = 0; i < M; i++)

                 {

                         char buf[11];

                         cin >> buf;

                         result += countKeys(trie, buf);

                 }

                 cout << result << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

참고: [프로그래밍 대회에서 배우는 알고리즘 문제해결전략]