백준[5670] 휴대폰 자판

문제 설명

문제 링크

https://www.acmicpc.net/problem/5670

풀이

트라이를 이용하여 풀이할 수 있다.

어느 지점까지 입력하였을 때 나올 수 있는 경우의 수가 1인 경우 자동으로 입력을 해줘야 한다. 그러기 위해서 자식 노드의 수가 1개인 경우에 자동 입력을 해야 한다. 또한 hello hell와 같이 문자열의 앞부분이 동일한 경우에 hello를 입력하기 위해서는 hell을 입력하고 o를 한번 더 입력해야 한다. 이 경우는 자식 노드가 1개이며 문자열이 끝나는 경우 한번 더 입력하게 한다.

Trie 구조체의 멤버로 Trie *nxt[26]으로 한번 구현하고 최적화를 위해 map으로 한번 더 구현했다.

코드

최적화x

#include <cstdio>
#include <cstring>

struct Trie {
    bool finish;
    int child;
    Trie *nxt[26];

    Trie() : finish(false), child(0) {
        memset(nxt, 0, sizeof(nxt));
    }

    ~Trie() {
        for (int i = 0; i < 26; i++) {
            if (nxt[i]) delete nxt[i];
        }
    }

    void insert(const char *key) {
        if (*key == 0) {
            finish = 1;
            return;
        }
        int idx = *key - 'a';
        if (!nxt[idx]) {
            child++;
            nxt[idx] = new Trie();
        }
        nxt[idx] -> insert(key + 1);
    }

    int find(const char *key) {
        if (*key == 0) return 0;
        int idx = *key - 'a';
        if (child > 1 || (child == 1 && finish)) return nxt[idx] -> find(key + 1) + 1;
        else return nxt[idx] -> find(key + 1);
    }
};

char ipt[100005][81];
int main() {
    int N;
    while (scanf("%d", &N) != EOF) {
        Trie *root = new Trie();
        for (int i = 0; i < N; i++) {
            scanf("%s", ipt[i]);
            root -> insert(ipt[i]);
        }
        int ret = 0;
        for (int i = 0; i < N; i++) {
            ret += root -> find(ipt[i]);
            if (root -> child == 1) ret++;
        }
        double ans = double(ret) / double(N);
        printf("%.2lf\n", ans);
        delete root;
    }
}

최적화o

#include <cstdio>
#include <cstring>
#include <map>

using namespace std;

struct Trie {
    bool finish = false;
    int child = 0;
    map<char, Trie> next;

    Trie() : finish(false), child(0) { }

    void insertTrie(const char *key) {
        if (*key == 0) {
            finish = true;
            return;
        }
        if (this -> next.find(*key) == this -> next.end()) {
            this -> next[*key] = Trie();
            child++;
        }
        this -> next[*key].insertTrie(key + 1);
    }

    int search(const char *key) {
        if (*key == 0) return 0;
        if (child > 1 || (child == 1 && finish)) return next[*key].search(key + 1) + 1;
        else return next[*key].search(key + 1);
    }
};

char ipt[100005][81];

int main() {
    int N; while (scanf("%d", &N) > 0) {
        Trie root = Trie();
        for (int i = 0; i < N; i++) {
            scanf("%s", ipt[i]);
            root.insertTrie(ipt[i]);
        }
        int ret = 0;
        for (int i = 0; i < N; i++) {
            ret += root.search(ipt[i]);
            if (root.child == 1) ret++;
        }
        double ans = double(ret) / double(N);
        printf("%.2lf\n", ans);
    }
}

위: map 아래: nxt[26]

map을 사용하면 메모리를 절반으로 줄일 수 있다.