[BOJ] 5670 : Cellphone Typing

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

---

트라이 Trie

  자료구조 트라이를 이용하는 문제입니다.

 1) 들어오는 모든 문자열을 insert 해서 트라이를 만듭니다.

 2) 문자열을 하나씩 트라이에서 탐색을 수행합니다.

   2-1) 현재 첫 번째 글자라면 무조건 버튼을 눌러야 하므로 다음 글자로 넘어가며 카운트를 증가합니다.

   2-2) 현재 글자에서 다음 글자로 가는 길이 2가지 이상이거나 혹은 현재 글자에서 끝난 문자열이 있다면 버튼을 눌러야 하므로 다음 글자로 넘어가며 카운트를 증가합니다.

   2-3) 위의 경우가 아니라면 자동으로 입력되므로 카운트를 증가시키지 않고 다음 글자로 탐색을 진행합니다.

 

 알고리즘은 위와 같이 간단합니다. 하지만, EOF가 입력될 때까지 매번 트라이를 구현해야하는 문제로, delete 를 하지 않는다면 메모리 초과가 발생합니다.

#include<iostream>
#include<string>
#include<vector>
#include<cstring>
#include<algorithm>

using namespace std;

struct Trie {
	bool finish;    //끝나는 지점을 표시해줌
	Trie* next[26];    //26가지 알파벳에 대한 트라이
	Trie() {
		finish = false;
		memset(next, 0, sizeof(next));
	}
	~Trie() {
		for (int i = 0; i < 26; i++)
			if (next[i])
				delete next[i];
	}

	void insert(const char* key) {
		if (*key == '\0')
			finish = true;    //문자열이 끝나는 지점일 경우 표시
		else {
			int curr = *key - 'a';
			if (next[curr] == NULL)
				next[curr] = new Trie();    //탐색이 처음되는 지점일 경우 동적할당
			next[curr]->insert(key + 1);    //다음 문자 삽입
		}
	}

	int find(const char* key, int cnt) {
		if (*key == '\0')
			return cnt;
		if (cnt == 0)
			return next[*key - 'a']->find(key + 1, cnt + 1);

		int check = 0;
		for (int i = 0; i < 26; i++)
			if (next[i] != NULL)
				check++;


		if (check > 1 || finish) // 가는 길이 2가지 이상
        		cnt++;
        return next[*key - 'a']->find(key + 1, cnt);
	}
};

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	while (1) {
		int N;
		cin >> N;
		if (cin.eof())
			break;
		Trie* trie = new Trie();

		vector<string> list(N);
		for (int i = 0; i < N; i++){
			cin >> list[i];
			trie->insert(list[i].c_str());
		}
        
		int total = 0;
		for (int i = 0; i < N; i++)
			total += trie->find(list[i].c_str(), 0);

		cout << fixed;
		cout.precision(2);
		cout << double(total) / double(N) << '\n';
        
        delete trie;
	}
	return 0;
}

---