백준 No.5670 [휴대폰 자판]

BOJ No.5670 [휴대폰 자판]

---

  문제 

5670번: 휴대폰 자판 (acmicpc.net)

5670번: 휴대폰 자판

---

  설명 

 <알고리즘 분류> 
 * 자료 구조
 * 트라이 (Trie)

  문자열을 저장하는 자료구조 (Trie : 트라이 (Trie) : 문자열 저장 자료구조) 를 이용하는 문제이다.

 

  각 Node 의 옆에 파란 숫자는 그 글자까지 나오기까지 키보드를 누른 횟수이다. 또한 빨간 테두리 Node 는 단어의 끝을 알리는 Node 이다.

 

  키보드를 누르는 경우는 크게 세 가지가 있다.

1. 아직 아무 문자도 안 눌린 경우 (root Node)
2. 자식 Node 가 두 개인 경우
    - 위 예시로 'k' 문자에 해당되는 Node 이다.
3. 현재 Node 를 끝으로 단어가 하나 생성이 되면서, 다음 Node 가 또 존재하는 경우
    - 위 예시로 "hi" 단어가 끝난 후 이어서 "hint" 단어가 생성되는 경우이다.

  위 Trie 자료 구조에서 위 세 가지 경우가 있을 때 마다 Count 횟수가 늘어나는 것을 볼 수 있다.

 

  기존 Trie 자료 구조에 해당되는 Class 들에 위 작업에 해당되는 함수를 추가로 구현함으로써 해결할 수 있다. 아래 코드에서는 check 함수와 check_in 함수가 이 문제 해결의 중심이 된다.

 

 <정리> 
  기존 Trie 자료 구조 Class 에서 각 Node 에 대해 현재까지 키보드가 눌린 횟수를 Check 하는 작업을 진행하면 된다.
  눌린 횟수는 아래 세 가지 경우에 의해 파악한다.

  1. 아직 아무 문자도 안 눌린 경우 (Root Node)
  2.  자식 Node가 두 개인 경우
  3. 현재 Node를 끝으로 단어가 하나 생성이 되면서, 다음 Node가 또 존재하는 경우

---

  Code 

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

using namespace std;

int n;

class Node {
public:
	Node* child[26];
	char curWord;
	int childCnt;
	bool isEnd;

	Node() : curWord('.'), childCnt(0), isEnd(false) {
		for (int i = 0; i < 26; i++)
			child[i] = NULL;
	}
};

class Tri {
public:
	Node* root = new Node;
	int cntSum;				// 현재 Trie 자료 구조에서 총 count 값에 대한 변수

	Tri() : cntSum(0) {};
	~Tri() {
		Delete(root);
	}

	void push(string& str) {
		insert(str, 0, root, NULL);
	}

	int check() {
		check_in(root, 0);
		return cntSum;
	}

private:
	void insert(string& str, int index, Node* curNode, char CUR_WORD) {
		curNode->curWord = CUR_WORD;
		if (str.length() == index) {					// 입력된 단어의 끝 이라면
			curNode->isEnd = true;						//   현재 Node를 단어의 끝이라 하고
			return;										//   끝낸다.
		}

		char nextWord = str[index];						// 다음 자식 Node에 해당되는 문자

		if (curNode->child[nextWord - 'a'] == NULL) {	// child Node 없는 경우
			curNode->childCnt++;						// child count 증가시키고
			curNode->child[nextWord - 'a'] = new Node;	// memory 할당
		}

		insert(str, index + 1, curNode->child[nextWord - 'a'], nextWord);
	}

	void check_in(Node* curNode, int cnt) {
		if (curNode->isEnd) {	// 이 Node를 끝으로 하는 단어가 있을 때
			if (curNode->childCnt) {	// 그런데 다음 Node 또한 있을 때
				cntSum += cnt;
				for (int i = 0; i < 26; i++) {
					if (curNode->child[i] != NULL)
						check_in(curNode->child[i], cnt + 1);
				}
			}
			else cntSum += cnt;			// 그게 아니라면 이 단어를 끝으로 더이상 문자가 없을 때
			return;	
		}

		for (int i = 0; i < 26; i++) {
			if (curNode->child[i] != NULL)
				check_in(curNode->child[i], cnt + (curNode == root? 1 : (1 < curNode->childCnt ? 1 : 0)));
		}
	}

	void Delete(Node* curNode) { // Memory 상에서 모든 Node 들을 Delete 하는 함수
		for (int i = 0; i < 26; i++) {
			if (curNode->child[i] != NULL)
				Delete(curNode->child[i]);
		}
		delete curNode;
	}
};

int main() {
	cout << fixed;
	cout.precision(2);

	string str;
	while (cin >> n) {
		Tri* tri = new Tri;

		for (int i = 0; i < n; i++) {
			cin >> str;

			tri->push(str);
		}

		int sum = tri->check();
		cout << double(sum) / double(n) << '\n';

		delete tri;
	}
}