(라이님 블로그 대회 알고리즘 따라잡기 32) Trie

오늘은 Trie에 대해 알아보았다. 늘 그렇듯 설명은 라이님 블로그 Trie를 참고하면 된다.

이번 알고리즘은 내용도 직관적이고, 코드도 짧아 좋았다@@

 

#include <cstdio>
#include <memory>
#include <cstring>
using namespace std;
constexpr int SIZE = 10; // 0-9까지 총 10개의 숫자

struct Trie {
	unique_ptr<Trie> child[SIZE];
	bool isEnd;       // 현재 노드가 전화번호의 끝인지 여부
	bool hasChild;    // 현재 노드가 자식을 가지고 있는지 여부

	// 생성자 
	Trie() : isEnd(false), hasChild(false) {}

	// 전화번호를 트라이에 삽입하고, 일관성이 유지되는지 확인
	bool insert(const char* num) {
		if (*num == '\0') {
			isEnd = true;
			return !hasChild;  // 자식이 있다면 일관성 깨짐
		}

		int idx = *num - '0';
		if (!child[idx]) child[idx] = make_unique<Trie>();
		hasChild = true;

		return !isEnd && child[idx]->insert(num + 1);
	}
};

int main() {
	int T; scanf("%d", &T);
	while (T--) {
		int n; scanf("%d", &n);
		auto root = make_unique<Trie>();
		bool consistent = true;

		for (int i = 0; i < n; i++) {
			char num[11]; scanf("%s", num);
			if (consistent && !root->insert(num)) consistent = false;
		}
		puts(consistent ? "YES" : "NO");
	}
	return 0;
}

 

#include <cstdio>
#include <algorithm>
#include <memory>

using namespace std;

struct Node {
    std::unique_ptr<Node> child[26];  // 자식 노드 배열
    bool isEnd;  // 현재 노드가 단어의 끝인지 여부
    int numChildren; // 가지, 즉 자식 노드의 개수
    int numWords; // 현재 노드의 서브트리에 있는 단어의 개수

    // 생성자
    Node() : isEnd(false), numChildren(0), numWords(0) {}

    // 단어를 트라이에 삽입하는 함수
    void insert(const char* str) {
        if (*str == '\0') {
            isEnd = true;
        } else {
            int idx = *str - 'a';
            if (!child[idx]) {
                numChildren++;
                child[idx] = std::make_unique<Node>();
            }
            child[idx]->insert(str + 1);
            numWords++;  // 자식 노드 삽입 후에도 서브트리 내 단어 개수를 증가
        }
    }

    // 현재 노드에서 필요한 총 타이핑 횟수를 세는 재귀 함수
    long long calculateKeystrokes(bool isRoot = false) {
        long long result = 0;
        // 루트 노드이거나 현재 노드에서 여러 단어로 갈 수 있는 경우 타이핑 횟수 추가
        if (isRoot || numChildren > 1 || (numChildren == 1 && isEnd)) {
            result = numWords;
        }
        // 각 자식 노드에 대해 재귀적으로 타이핑 횟수 계산
        for (int i = 0; i < 26; i++) {
            if (child[i]) {
                result += child[i]->calculateKeystrokes();
            }
        }
        return result;
    }
};

int main() {
    int n;
    while (scanf("%d", &n) > 0) {
        auto root = std::make_unique<Node>();
        for (int i = 0; i < n; i++) {
            char word[81];
            scanf("%s", word);
            root->insert(word);
        }
        printf("%.2lf\n", 1.0 * root->calculateKeystrokes(true) / n);
    }
}