[BOJ] 5670 : 휴대폰 자판

5670 : 휴대폰 자판

풀이

트라이 자료구조 이용

문제점

1.1초제한에 900ms로 겨우 통과했다.

2.메모리초과가 계속나다가 deleteTrie(Root) 해주니까 통과가 되었다.

트라이 자료구조 사용방법에 대해서는 잘 배웠고,

같은 트라이라도 find를 설계하기 따라 속도가 빨라질수 있는것같다.

다른알고리즘도 살펴봐야겠다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <stack>
using namespace std;

char words[100002][82];

const int trieNum = 27;
int cnt;

struct Trie {
    bool finish;
    Trie *next[trieNum];
    Trie() :finish(false) {
        for (int i = 0; i < trieNum; i++)
            memset(next, 0, sizeof(next));
    }
    ~Trie() {
        for (int i = 0; i < trieNum; i++) {
            if (next[i]) 
                delete next[i];
        }
    }

    void insert(const char *arr) {
        if (*arr == '\0')
            finish = true;
        else {
            int cur = *arr - 'a';
            if (next[cur] == NULL) {
                next[cur] = new Trie();
            }
            next[cur]->insert(arr + 1);
        }
    }
    
    void find(const char *arr) {
        //문자열이 끝남
        if (*arr == '\0')
            return;
        int cur = *arr - 'a';
        char flag = *(arr + 1);
        if (flag == '\0') {
            //cout << "OK" << '\n';
            return;
        }
        int childNum = 0;
        if (next[cur]->finish)
            childNum++;
        for (int i = 0; i < trieNum; i++) {
            if (next[cur]->next[i] != NULL) {
                childNum++;
            }
        }
        if (childNum <= 1) {
            next[cur]->find(arr + 1);
        }
        else {
            cnt++;
            next[cur]->find(arr + 1);
        }
    }
};

void deleteTrie(Trie *R) {
    if (R == 0)return;

    delete R;
    R = 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    while (cin>>n) {
        memset(words, 0, sizeof(words));

        for (int i = 0; i < n; i++) {
            cin >> words[i];
        }
        Trie *Root = new Trie();
        for (int i = 0; i < n; i++)
            Root->insert(words[i]);

        cnt = 0;
        for (int i = 0; i < n; i++) {
            cnt++;
            Root->find(words[i]);

        }
        
        double avg = (double)cnt / n;
        cout << fixed;
        cout.precision(2);
        cout << avg << '\n';
        deleteTrie(Root);
    }
    return 0;
}
Written on August 10, 2019