백준 #4358 생태학


BOJ #4358 - 생태학

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

# 문제 분류

Trie + map

풀이 접근 방법


트라이랑 맵을 이용해서 해당 종이 몇번 나오는지 마지막 노드로 체크할 수 있게 했다.


#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <vector>

#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define fup(i, a, b, c) for (int(i) = (a); (i) <= (b); (i) += (c))
#define fdn(i, a, b, c) for (int(i) = (a); (i) >= (b); (i) -= (c))
#define endl "\n"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const ll MOD = 1e9 + 7;
const int stMAX = 1 << 18;
const int INF = 1e9;
char tmp[40];

const int trie_MAX = 300;

struct Trie {
    int end;
    Trie *ptr[trie_MAX];

    Trie() {
        fill(ptr, ptr + trie_MAX, nullptr);
        end = 0;
    }

    void insert(const char *str) {
        if (*str == 0)
            end++;
        else {
            int next = *str;
            if (!ptr[next]) {
                ptr[next] = new Trie;
            }
            ptr[next]->insert(str + 1);
        }
    }

    int search(const char *str) {
        if (*str == 0) {
            return end;
        } else {
            int next = *str;
            if (!ptr[next]) {
                return -1;
            }
            return ptr[next]->search(str + 1);
        }
    }
};

int main() {
    Trie t;
    vector<string> v;
    map<string, int> m;
    int cnt = 0;
    int N = 0;

    while (fgets(tmp, 35, stdin) != NULL) {
        if (tmp[strlen(tmp) - 1] == '\n')
            tmp[strlen(tmp) - 1] = '\0';
        t.insert(tmp);
        string s = tmp;

        N++;

        if (!m.count(s)) {
            m[s] = cnt;
            v.pb(s);
            cnt++;
        }
    }

    sort(v.begin(), v.end());
    for (string p : v) {
        const char *arr = p.c_str();
        cout << p << " ";
        double res = t.search(arr) / (double)N * 100;

        cout << fixed;
        cout.precision(4);
        cout << res << endl;
    }
}