[SW Expert Academy] 호둥이의 단어 찾기

4753. 호둥이의 단어 찾기

SW Expert academy 문제는 저작권 문제가 있기 때문에 링크로 대체하겠습니다!

이 문제에서 가장 중요한 부분은 

1. 사전 순으로 탐색한다.

2. 둘이 다른 구간을 만나거나 똑같으면 종료된다.

3. 만약, 사전에 단어가 있다면 뒤의 단어들은 사용하지 않는다.

입니다. 

저는 문제를 풀 때 트라이를 활용하면 될 것 같다고 생각했습니다!

우선 트라이는 위 그림과 같이 문자열의 알파벳을 하나하나 저장하는 구조입니다! a와 b를 저장한 것을 구분하기 위해 테두리를 두껍게 했습니다! 그럼 이와 같은 트라이를 어떻게 활용하면 이 문제를 해결할 수 있을까요?!

1 4 abc abd a ab 3 abcd a ab

위 입력을 예시로 설명해드리도록 하겠습니다!

테스트 케이스에서 abcd를 찾는 경우를 생각해봅시다.

abcd를 트라이로 찾아가는 과정으로 생각해보죠!

길이가 0인 단어의 개수! 즉, 모든 단어의 개수는 4개 입니다.

a에서 길이가 1인 단어들은 4개 입니다.

b로 가고 길이가 2인 단어들은 ab, abc, abd 세 종류가 있죠!

이제 abc로 가면 abc 하나의 단어만 남습니다! 그리고 abcd라는 단어는 존재하지 않죠.

자! 그럼 이제 거꾸로 올라가면서 연산을 몇 번 했는지 알 수 있습니다.

우선, abc까지 같은 단어가 하나였죠!?

abc까지 같은 단어였다는 말은, abc 공백문자와 d문자를 비교한다는 것 입니다!

즉, 길이가 3개가 같은 단어가 있다면, 이 단계에 있는 단어들은 4번의 비교 연산을 하는 것입니다!

만약, abcd가 있었다면, 길이가 4개인 단어를 탐색하고, 5 번의 비교 연산을 수행할 것 입니다!

즉, 비교 연산을 해당 트라이의 길이 + 1번 만큼 수행하는 것이죠!

그리고 b까지는 ab, abc, abd 3개가 있었죠!?

하지만,  abc는 이미 길이 3에서 처리했습니다!

즉, 다음 단어에서 처리한 개수에서 현재의 개수를 빼준 만큼 연산을 할 것입니다!

길이는 2이기 때문에 3개 - 1개 = 2 개의 단어, 즉 ab와 abd가 abcd와 3번의 비교연산을 하겠죠!

현재까지 총 4 + 3*2 = 10번 연산을 했습니다!

이렇게 마찬가지로 길이가 1인 곳에서는 a와 abcd가 2번의 연산을 하겠죠!

abcd는 총 12번의 연산을 하는 것입니다!

하지만 a의 경우는 어떨까요!?

a는 사전에 존재하는 인덱스입니다! 심지어 ab는 a보다 순서상 뒤에있기 때문에 연산을 해서는 안되죠!

하지만, 현재의 방법으론 그것을 구분할 수가 없습니다!

새로운 방법이 필요해보입니다.

해결 방법은 간단합니다!

'해당 트라이에서 자신이 몇 번째'인지 저장하는 저장 공간을 새로 만들면 됩니다!

그리고, 이 방법 또한, 트라이를 삽입하면서 이미 트라이에 몇개의 트라이가 있는지 저장되어 있다면 쉽게 알 수 있습니다!

이번엔 트라이를 만들 때를 예시로 들겠습니다!

자! abc 트라이를 만듭니다. 아직 아무 트라이도 존재하지 않기 때문에, abc는 0,1,2,3에서 각각 첫번째 자리에 있다는 것을 알 수 있습니다!

abd는 어떨까요?! 0번, 1번, 2번 자리에는 이미 a와 b가 크기 1을 가진다는 것을 알 수 있습니다.

따라서, abd의 위치는 2,2,2,1이 됩니다.

이와 같은 방법으로 a도 만들고

ab도 만듭니다!

이렇게 만든 자료를 가지고 다시 한번 a를 몇 번이나 연산하는 지 알아봅시다!

a를 검사했는데, a가 끝이라고 합니다! 즉, a는 존재하는 문자열입니다!

끝이 a라는 정보가 트라이에 담겨있기 때문에, a는 0번자리, 1번 자리에서 3번째 라는 것을 알 수 있습니다.

길이가 1이기 때문에, 2번 연산을 할 것이고, 글자가 3개이기 때문에 총 6번의 연산을 수행할 것입니다!

그리고 길이 0으로 올라가면, 마찬가지로 3개가 존재하지만, 이미 길이 1인 곳에서 모두 처리했기 때문에 아무 연산도 하지 않습니다.

그러면 a는 총 6번의 연산을 했다는 것을 알 수 있는 것이죠!

1 4 abc abd a ab 3 abcd a ab

다시 한번 위의 테스트 케이스로 연산을 수행해볼까요?

abc

a공백 

으로 2번,

abd

a공백

으로 2번,

a공백

a공백

으로 2번 그리고 종료됩니다!

총 6번이 되고, 이는 트라이로 구했던 수와 정확하게 일치합니다!

즉, 해당 글자가 끝이 된다면, 해당 인덱스를 기준으로 문자수를 처리하면 됩니다! 어짜피 뒤의 인덱스들은 연산을 수행하지 않기 때문이죠!

만약, 해당 글자가 끝이 안되고 다음 트라이로 이동할 수 없거나, 찾고자 하는 문자열이 먼저 끝나버린 경우에는 사전에 해당 문자열이 존재하지 않는다는 것입니다.

이 때는 abcd에서 보여줬던 예처럼 그냥 트라이에 저장되어 있는 크기를 이용하여 몇 번의 연산을 수행하게 될지 찾아나가면 됩니다!

코드

#pragma once
#include<cstring>
#include<cstdio>
 
int sn, m;
 
char conv[256], str[31];
int cnts[30000][31];
 
struct TNODE {
    int end, num;
    TNODE* nodes[26];
    TNODE() {
        num = 0;
        end = -1;
        for (int i = 0; i < 26; i++) nodes[i] = NULL;
    }
} tnodes[900000];
 
struct MYAL {
    int i;
    const int SIZE = 900000;
    MYAL() {
        i = 0;
    }
    
    TNODE* alloc() {
        if (i == SIZE) return NULL;
        return &tnodes[i++];
    }
 
    void clear() {
        for (int j = 0; j < i; j++) {
            for (int k = 0; k < 26; k++) {
                tnodes[j].nodes[k] = 0;
            }
            tnodes[j].end = -1;
            tnodes[j].num = 0;
        }
        i = 0;
    }
}al;
 
struct TRIE {
    TNODE n;
    long long res, idx;
 
    long long find(const char* str) {
        res = 0;
        idx = -1;
        allFind(&n, str, 0);
        
        return res;
    }
 
    void insert(const char* str, int idx) {
        insert(&n, str, idx,0);
    }
 
    void insert(TNODE *n, const char* str, int idx, int depth) {
        //단어의 끝
        if (*str == 0) {
            n->end = idx; // 해당 단어의 끝이 있다
            cnts[idx][depth] = ++(n->num); //해당 문자열이 트라이의 몇번 째 방문자인지 삽입
            
            return;
        }
 
        // 없는 트라이면 새로 할당
        if (n->nodes[conv[*str]] == 0) {
            n->nodes[conv[*str]] = al.alloc();
        }
 
        cnts[idx][depth] = ++(n->num);
 
        insert(n->nodes[conv[*str]], str + 1, idx, depth + 1);
    }
 
    int allFind(TNODE* n, const char* str, int depth) {
        //단어의 끝
        if (*str == 0) {
            idx = n->end; //단어가 사전에 존재하면 해당 인덱스가 저장된다. 존재하지 않는다면 -1
            int ret = idx == -1 ? n->num : cnts[idx][depth]; // 존재하지 않으면, 처음부터 끝까지 모든 단어를 보면된다.
            res = ret * (depth+1);
 
            return ret; //처리된 문자열 개수이다.
        }
 
        int sum = 0;
        sum = n->nodes[conv[*str]] ? allFind(n->nodes[conv[*str]], str + 1, depth + 1) : 0; // 이미 처리된 단어 수를 반환받는다.
        int ret = idx == -1 ? n->num : cnts[idx][depth];                                     // 만약, 사전에 존재하지 않으면 처음부터 끝까지 모든 단어를 보고, 아니라면
                                                                                            // 해당 인덱스까지 몇 개의 단어가 존재하는지만 보면 된다.
 
        res += (ret - sum)*(depth+1); // 아직 처리 안된 단어들은 현재 처리할 수 있는 단어 - 이미 처리한 단어 수이다.
        return ret; //처리한 단어를 반환한다.
    }
    void clear() {
        for (int i = 0; i < 26; i++) {
            n.nodes[i] = NULL;
        }
        n.num = 0;
    }
} trie;
 
void init() {
    for (char i = 'a'; i <= 'z'; i++) {
        conv[i] = i - 'a';
    }
}
 
void set()
{
    scanf("%d\n", &sn);
    memset(cnts, 0, sizeof(cnts));
 
    trie.clear();
    al.clear();
 
    for (int i = 0; i < sn; i++) {
        scanf("%s\n", str);
        trie.insert(str, i);
    }
 
    scanf("%d\n", &m);
}
 
int main() {
    int t;
    scanf("%d\n", &t);
    
    init();
    
    for (int tc = 1; tc <= t; tc++) {
        set();
        long long res = 0, res2 = 0;
        
        while (m--) {
            scanf("%s\n", str);
 
            res += (long long)trie.find(str);
        }
 
        printf("#%d %lld\n", tc, res); 
    }
    return 0;
}

여담

시간 복잡도는 트라이를 만드는데 N개의 문자열 시간만큼 걸리고, 결과를 출력하는데에도 M의 시간이 걸리기 때문에

선형 시간인

O(N + M)이 됩니다! 짧군요!