C++ / 백준 / 5670 / 휴대폰 자판

문제

 

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

5670번: 휴대폰 자판

 

문제풀이

 

트라이 문제이다.

첫 글자를 제외하고 전 글자와 연결되는 이번 글자가 하나뿐이라면 버튼 입력 없이 자동으로 입력해 준다.

모든 단어를 입력할 때 버튼을 총 몇 번 눌러야 되는지를 단어 개수로 나누어 소수점 둘째 자리까지 출력하면 된다.

 

문제를 풀면서 메모리 초과와 출력 초과를 겪었다.

메모리 초과문제는 테스트케이스가 여러 개이기 때문에 한 테스트케이가 끝나면 소멸자를 통해 delete를 하여 해결했다.

출력 초과는 처음에는 while(1) 안에서 cin >> N을 통해 N을 입력받았는데 while(cin >> N)으로 바꾸니 통과됐다.

 

메인문에서는 크게 적을 것이 없다. 입력을 받고 트라이를 구성하고, 모든 트라이 구성이 끝났으면 단어 하나씩 탐색을 하면 된다.

 

	void insert(string& s) {
		Trie* now = this;
		for (int idx = 0; idx < s.size(); ++idx) {
			if (now->child[s[idx] - 'a'] == nullptr) {
				now->child[s[idx] - 'a'] = new Trie();
				++now->cnt;
			}
			now = now->child[s[idx] - 'a'];
			if (idx + 1 == s.size()) now->isEnd = true;
		}
	}

트라이를 구성하는 insert 함수이다.

비어있으면 새로운 트라이를 생성하고 부모 트라이에 자녀 트라이의 개수를 1씩 더한다.

그다음 자녀 트라이로 넘어가고 반복한다.

 

	void search(string& s) {
		Trie* now = this;		
		bool prev(true);		
		for (int idx = 0; idx < s.size(); ++idx) {
			if (prev == false && now->cnt == 1)
				--total;

			if (now->child[s[idx] - 'a'] != nullptr)
				now = now->child[s[idx] - 'a'];
				
			if (now->isEnd == true)	prev = true;
			else prev = false;
		}
	}

문자열을 탐색하는 함수이다.

메인 문에서 총 터치 개수를 모든 문자열의 문자 개수를 더해 미리 구해놓았다.

prev 변수는 부모 트라이에서 끝난 단어가 있는지를 판별하는 변수이다.

만약 부모 트라이가 끝난 단어가 아니고 자녀 트라이가 하나밖에 없다면, 이번 문자는 자동 완성 문자이므로 개수에서 하나를 빼준다.

 

예제에서 structure를 보면

s는 첫 글자이므로 누른다.

t는 st와 so가 있기 때문에 눌러야 한다.

r은 str 밖에 없으므로 자동완성이 된다.

u는 stru와 stre가 있기 때문에 눌러야 한다.

c는 struc 밖에 없으므로 자동완성이 된다.

t는 struct 밖에 없으므로 자동완성이 된다.

u는 structu 밖에 없으므로 자동완성이 된다.

r은 structur 밖에 없으므로 자동완성이 된다.

e는 structure 밖에 없으므로 자동완성이 된다.

s는 structures 밖에 없지만 structure에서 끝나는 단어가 있으므로 이전 단계에서 structure까지밖에 자동완성이 안된다.

따라서 s는 추가적으로 눌러야 한다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int total;

struct Trie {
	Trie* child[26];
	int cnt;
	bool isEnd;

	Trie() :child(), cnt(0), isEnd(false) {}
	~Trie() {
		for (int idx = 0; idx < 26; ++idx) {
			if (child[idx]) delete child[idx];
		}
	}

	void insert(string& s) {
		Trie* now = this;
		for (int idx = 0; idx < s.size(); ++idx) {
			if (now->child[s[idx] - 'a'] == nullptr) {
				now->child[s[idx] - 'a'] = new Trie();
				++now->cnt;
			}
			now = now->child[s[idx] - 'a'];
			if (idx + 1 == s.size()) now->isEnd = true;
		}
	}

	void search(string& s) {
		Trie* now = this;		
		bool prev(true);		
		for (int idx = 0; idx < s.size(); ++idx) {
			if (prev == false && now->cnt == 1)
				--total;

			if (now->child[s[idx] - 'a'] != nullptr)
				now = now->child[s[idx] - 'a'];
				
			if (now->isEnd == true)	prev = true;
			else prev = false;
		}
	}

};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N(0);

	while (cin >> N) {		
		vector<string>dict(N, "");
		total = 0;
		Trie* trie = new Trie();
		for (int idx = 0; idx < N; ++idx) {
			cin >> dict[idx];
			trie->insert(dict[idx]);
		}
		
		for (int idx = 0; idx < N; ++idx) {
			trie->search(dict[idx]);
			total += dict[idx].size();
		}

		cout << fixed;
		cout.precision(2);
		cout << (double)total / N << '\n';

		delete trie;
	}
}