[BOJ] 휴대폰 자판(5070)

[백준(BOJ)] 휴대폰 자판(5070) C++

문제 : BOJ_5070번 휴대폰 자판

문제 설명

Trie(트라이)

트라이로 해결하는 문제입니다.
입력한 문자열 다음의 문자가 저장된 문자열 중 하나밖에 없을 경우 자동으로 입력해 주고,
다음의 문자열이 하나 이상이거나, 입력을 멈출 때는 사용자가 입력을 해주어야 합니다.
이때 모든 문자에서 사용자가 입력해야 하는 입력의 평균 횟수를 구해야 합니다.


Solution

우선 기존 트라이의 공식을 이용해서 트라이 구조체 안에 모든 문자열을 넣어줍니다.
그 뒤에 각 문자열마다 한 번씩 for문을 돌리며 입력해야 하는 횟수를 저장합니다.
저장된 다음 문자가 2개 이상이거나, 끝나는 문자열일 경우 횟수를 저장합니다.
이때, 문제의 조건에서 처음에는 반드시 1회 문자를 입력해야 하므로, 항상 첫 문자에서 횟수가 1이 더해져야 하는데, 모든 문자열의 첫 글자가 같을 시에는 1이 더해지지 않으므로, 그 경우만 따로 횟수를 1씩 더해주면 됩니다.


Description

  1. 테스트 케이스의 수가 지정되지 않음으로 EOF를 사용해야 합니다. (while (scanf(“%d”,&N) != EOF))
  2. char word[100001][81]는 할당 크기가 크므로 지역변수가 아닌 전역변수로 선언합니다.
  3. 테스트 케이스가 쌓일 수 있으므로, Trie를 삭제해 주어야 합니다.(delete trie)
  4. 모든 문자열의 첫 문자가 같은 경우엔 전체 개수에서 N을 더해주었습니다.

#include <iostream>
using namespace std;
struct Trie {
	Trie* childTrie[26];
	bool isWord;
	int childCnt;
	Trie() {
		for (int i = 0; i < 26; i++) childTrie[i] = nullptr;
		isWord = false;
		childCnt = 0;
	}
	~Trie() {
		for (int i = 0; i < 26; i++) {
			if (childTrie[i]) delete childTrie[i];
		}
	}
	void insert(char* word) {
		if (*word == '\0') {
			isWord = true;
			return;
		}
		int nextNum = *word - 'a';
		if (childTrie[nextNum] == NULL) {
			childTrie[nextNum] = new Trie();
			childCnt++;
		}
		childTrie[nextNum]->insert(word + 1);
	}
	int check(char* word, int cnt) {
		if (*word == '\0') return cnt;
		if (childCnt > 1 || isWord) cnt++;
		int nextNum = *word - 'a';
		return childTrie[nextNum]->check(word + 1, cnt);
	}
};
int N;
char word[100001][81];
// 전역변수로 선언 (사이즈가 크므로)
int main(void) {
	while (scanf("%d",&N) != EOF) {
		// EOF 사용
		Trie* trie = new Trie();
		for (int i = 0; i < N; i++) {
			scanf("%s", word[i]);
			trie->insert(word[i]);
		}
		int result = 0;
		if (trie->childCnt == 1) result += N;
		// 전체 문자열의 첫 글자가 같은 경우 N 더해주기
		for (int i = 0; i < N; i++) {
			result += trie->check(word[i],0);
		}
		printf("%.2f\n", (double)result / N);
		delete trie;
		// 삭제
	}
	return 0;
}