[PS] 휴대폰 자판/ C++ (백준 5670번)

 

 

개미굴에서 EOF, 소수점 처리가 포함된 변형 문제

while (cin >> n)로 EOF 처리, 소수점 처리 잘 해주고 Trie에 size라는 변수, find 함수에 적당한 식을 추가하면 쉽게 해결할 수있음

메모리 초과가 났지만 소멸자가 제대로 작동하지 않았음 >> 소멸자 잘 작동하게 수정하니 바로 해결됨 

 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

char d[100001][81];

struct Trie {
	bool finish;
	int size;
	Trie* next[26];

	Trie() :finish(false),size(0) {
		memset(next, 0, sizeof(next));
	}

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

	void insert(char* key) {
		if (*key == '\0') {
			finish = true;
			return;
		}
		int cur = *key - 'a';
		if (next[cur] == NULL) {
			next[cur] = new Trie();
			size++;
		}
		next[cur]->insert(key + 1);
	}

	int find(char* key, int press) {
		if (*key == '\0') {
			return press;
		}
		int cur = *key - 'a';
		if ((size != 1 || finish == true) || press == 0)return next[cur]->find(key + 1, press + 1);
		else return next[cur]->find(key + 1, press);
	}

};

int main()
{
	int n;
	while (cin >> n) {
		Trie* tree = new Trie();
		int press = 0;
		for (int i = 0; i < n; i++) {
			scanf("%s", d[i]);
			tree->insert(d[i]);
		}
		for (int i = 0; i < n; i++) {
			press += tree->find(d[i], 0);
		}
		double dap = (double)press / n;
		printf("%.2lf\n", dap);
		memset(d, 0, sizeof(d));
		delete(tree);
	}
	return 0;
}