[C++] 백준 5670 휴대폰 자판

문제 링크

---

www.acmicpc.net/problem/5670

5670번: 휴대폰 자판

접근 방법

---

trie의 구조를 자식을 mapping할 수 있는 자기가신의 자료형과, 단어의 마지막인지 check하는 isFinished로 만들었다.

typedef struct Trie {
	bool isFinished;
	map<char, Trie> child;
};

trie의 삽입 과정은 어렵지 않으므로 자세한 설명없이 가장 밑에 소스코드로 첨부하겠다. 

문제를 해결해보자, 언제 우리는 타자를 쳐야할까? 

1. 트라이의 분기가 생길 때

2. 이미 딕셔너리에 포함된 단어를 포함하는 더 긴 단어를 입력할 때이다. 

 

아래 그림은 hell, hello, heaven, goodbye로 만든 trie구조이다.

1번은 아래 소스코드의 방법으로 확인 가능하다. 

 if (node.child.size() > 1 || idx == 0) {
	return inputCount(node.child[word[idx]], word, idx + 1) + 1;
}

(idx==0)인 경우는 현재 루트의 위치에 있을때이고, (node.child.size() > 1)인 경우는 자식이 최소 2개 이상일 때, 즉 분기점 이라는 것이다. 

 

2번은 아래 소스코드의 방법으로 확인 가능하다.

if (node.child.size() == 1 && node.isFinished == true) {
	return inputCount(node.child[word[idx]], word, idx + 1) + 1;
}

 (node.isFinished == true) && (node.child.size() == 1) -> 현재 탐색한 단어보다 더 긴 단어를 찾아갈 것이고, 현재 위치에서 끝난 단어가 있다는 뜻이다. 

소스 코드

---

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

using namespace std;

typedef struct Trie {
	bool isFinished;
	map<char, Trie> child;
};

void insert(Trie &node, string &word, int idx) {

	if (idx == word.size()) {
		node.isFinished = true;
		return;
	}
	if (node.child.count(word[idx]) == 0) {
		node.child[word[idx]] = Trie();
		node.child[word[idx]].isFinished = false;
	}
	insert(node.child[word[idx]], word, idx + 1);
}

int inputCount(Trie &node, string &word, int idx) {
	if (idx == word.size()) {
		return 0;
	}
	else if (node.child.size() > 1 || idx == 0) {
		return inputCount(node.child[word[idx]], word, idx + 1) + 1;
	}
	else if (node.child.size() == 1 && node.isFinished == true) {
		return inputCount(node.child[word[idx]], word, idx + 1) + 1;
	}
	else
		return inputCount(node.child[word[idx]], word, idx + 1);
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;

	while (cin >> n) {

		vector <string> words;
		int sum = 0;

		Trie trie;
		for (int i = 0; i < n; i++) {
			string word;
			cin >> word;
			words.push_back(word);
			insert(trie, word, 0);
		}
		for (int i = 0; i < words.size(); i++) {
			sum += inputCount(trie, words[i], 0);
		}
		cout << fixed;
		cout.precision(2);
		cout << double(sum)/words.size() << "\n";
	}
}

개발 환경 : Visual Studio 2019

질문, 덧글, 지적 환영합니다.