[BOJ] 5670 휴대폰 자판

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

 

 

Ries님의 블로그를 참고하여 문제를 풀었다

 

마지막에 생성한 trie를 할당 해제(delete root)를 안해줘서 메모리 초과가 났다 ㅠㅠ

입력 받을 때, while (scanf("%d", &n))로만 하면 출력 초과가 난다. -> while (scanf("%d", &n)>0)로 바꿔주면 됨

 

 

소스 코드:

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

int n;

struct trie {
	trie* next[26];
	int word, branch;

	trie() {
		fill(next, next + 26, nullptr);
		word = branch = 0;
	}
	~trie() {
		for (int i = 0; i < 26; i++) {
			if (next[i]) delete(next[i]);
		}
	}
	void insert(const char* key) {
		if (*key == '\0') {
			branch++;
			return;
		}
		word++;
		int num = *key - 'a';
		if (!next[num]) {
			next[num] = new trie();
			branch++;
            /*
            hello랑 hell가 있는 경우 
            hello를 치려면 hell에서 한 번 더 쳐야하므로 
            문자열이 끝난 경우 그 다음 trie의 branch를 +1 해준다
            */
		}

		next[num]->insert(key + 1);
	}
	long long func(bool isRoot = false) {
		long long res = 0;
		if (isRoot || branch > 1) res = word;
		for (int i = 0; i < 26; i++) {
			if (next[i]) res += next[i]->func();
		}
		return res;
	}
};

int main() {
	while (scanf("%d", &n)>0) {
		trie *root = new trie;
		for (int i = 0; i < n; i++) {
			char c[80];
			scanf("%s", c);
			root->insert(c);
		}
		printf("%.2lf\n", 1.0*root->func(true) / n);
		delete root;
	}
	return 0;
}