[BOJ] 5670 : 휴대폰 자판
풀이
트라이 자료구조 이용
문제점
1.1초제한에 900ms로 겨우 통과했다.
2.메모리초과가 계속나다가 deleteTrie(Root) 해주니까 통과가 되었다.
트라이 자료구조 사용방법에 대해서는 잘 배웠고,
같은 트라이라도 find를 설계하기 따라 속도가 빨라질수 있는것같다.
다른알고리즘도 살펴봐야겠다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <stack>
using namespace std;
char words[100002][82];
const int trieNum = 27;
int cnt;
struct Trie {
bool finish;
Trie *next[trieNum];
Trie() :finish(false) {
for (int i = 0; i < trieNum; i++)
memset(next, 0, sizeof(next));
}
~Trie() {
for (int i = 0; i < trieNum; i++) {
if (next[i])
delete next[i];
}
}
void insert(const char *arr) {
if (*arr == '\0')
finish = true;
else {
int cur = *arr - 'a';
if (next[cur] == NULL) {
next[cur] = new Trie();
}
next[cur]->insert(arr + 1);
}
}
void find(const char *arr) {
//문자열이 끝남
if (*arr == '\0')
return;
int cur = *arr - 'a';
char flag = *(arr + 1);
if (flag == '\0') {
//cout << "OK" << '\n';
return;
}
int childNum = 0;
if (next[cur]->finish)
childNum++;
for (int i = 0; i < trieNum; i++) {
if (next[cur]->next[i] != NULL) {
childNum++;
}
}
if (childNum <= 1) {
next[cur]->find(arr + 1);
}
else {
cnt++;
next[cur]->find(arr + 1);
}
}
};
void deleteTrie(Trie *R) {
if (R == 0)return;
delete R;
R = 0;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
while (cin>>n) {
memset(words, 0, sizeof(words));
for (int i = 0; i < n; i++) {
cin >> words[i];
}
Trie *Root = new Trie();
for (int i = 0; i < n; i++)
Root->insert(words[i]);
cnt = 0;
for (int i = 0; i < n; i++) {
cnt++;
Root->find(words[i]);
}
double avg = (double)cnt / n;
cout << fixed;
cout.precision(2);
cout << avg << '\n';
deleteTrie(Root);
}
return 0;
}
Written on August 10, 2019