백준 5670 휴대폰 자판

 

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

5670번: 휴대폰 자판

자동완성 기능이 있는 사전을 이용해 주어진 문자열들을 만들기 위해서는 몇 개의 알파벳을 입력하여야 하는가의 문제입니다. 

 

ex) hello, hell -> h 입력 시 hell 까지 자동 완성, hello, hell, he -> h 입력 시 he 까지 자동완성, l 입력 시 hell 까지 자동완성

 

트라이를 이용하여 다음과 같이 풀 수 있습니다. 

 

1) 입력으로 주어진 문자열의 마지막에 . 을 추가한다. (마지막 브랜치 분기 발생 체크용)

2) 각 문자열에 대해 트라이를 생성한다. (기존 트라이와 동일)

3) 각 문자열에 대해 검사한다.

- 첫 번째 문자는 반드시 검색하므로 검색 카운트 1부터 시작

- 현재 문자의 자식 트라이 노드가 NULL 이 아닌 것이 2개 이상 (즉, 브랜치 분기 발생) 시, 자식 노드가 . 이 아닌 경우 카운트 +1 후 검색 진행

- . 인 경우 종료 

 

이렇게 진행을 하게 되면 됩니다.

 

정리를 하고 보니 . 도 필요 없고, 문자열을 모두 다시 검색하지 않고 그냥 트라이 하나로 탐색이 가능한 걸 알게 되었습니다.... (나중에 좀 더 최적으로 풀어보기)

 

코드는 다음과 같습니다.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int n;
string s;
vector<int> result;
vector<string> vec;

class Trie {
	Trie* ch[27]; // 현재 알파벳에 대한 트라이 (마지막은 .)

public:
	Trie() {
		for(int i = 0; i < 27; i++) {
			ch[i] = NULL;
		}
	}

public:
	~Trie() {
		for(int i = 0; i < 27; i++) {
			if(ch[i] != NULL)
				delete ch[i];
		}
	}
	
public:
	void insert(const char* s) {
		// 문자 마지막 (.)
		if(*s == '.') {
			if(this->ch[26] == NULL)
				this->ch[26] = new Trie;
			this->ch[26]->insert(s+1);
			return;
		} 
		
		// 끝 도달 
		if(*s == 0) {	
			return;
		}
		
		int now = *s - 'a';
		
		if(ch[now] == NULL) {
			ch[now] = new Trie;
		}
		
		this->ch[now]->insert(s+1);
	}

public:
	void calc(const char* s, int res) {
		if(*s == 0) {
			result.push_back(res);
			return;
		}
		
		int now;
		if(*s != '.')
			now = *s - 'a';
		else 
			now = 26;
		
		int cnt = 0;
		if(now != 26) {
			for(int i = 0; i < 27; i++) {
				if(this->ch[now]->ch[i] != NULL)
					cnt++;
				if(cnt == 2)
					break;
			}
		}
		
		// 브랜치 생성 
		if(cnt == 2) {
			// . 아닌 경우 
			if(*(s+1) != '.') 
				this->ch[now]->calc(s+1, res+1);
			else 
				this->ch[now]->calc(s+1, res);
		}
		else {
			this->ch[now]->calc(s+1, res);
		}
	}
};

void init(Trie* trie)
{
	result.clear();
	vec.clear();
	
	for(int i = 0; i < n; i++) {
		cin >> s;
		s += '.';
		vec.push_back(s);
		trie->insert(s.c_str());
	}
}

void game(Trie* trie)
{
	for(auto v : vec) {
		trie->calc(v.c_str(), 1);
	}
	
	double res = 0;
	for(auto r : result) {
		res += (double)r;
	}
	
	printf("%.2f\n", res / (double)n);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	Trie* trie;
	while(cin >> n) {
		trie = new Trie;
		init(trie);
		game(trie);
		delete trie;
	}
}