[BOJ] 5670 휴대폰 자판

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

Note

핸드폰의 자동 완성 기능과 비슷한 프로그램을 만들었을 때 평균 몇 회의 시도를 해야하는지 출력하자.

여러 문자열을 처리 해야하는 문제다.
앞서 풀었던 문제는 정적으로 처리 했던 것과는 다르게 동적 메모리가 필요하다.
트라이를 정적 메모리로 잡고 있기에는 메모리 낭비가 너무 심하다.

각 자리의 도메인이 소문자이기 때문에 트라이의 차수는 소문자 갯수인 26
사실 트라이를 구성 하는거 까지는 오래 안걸렸는데. 결과값으로 유도하기 위한 부분에서 생각이 좀 필요했다.
트라이의 멤버 변수에 childCount를 추가해 현재 자식의 개수가 몇개인지 기억 하도록 해 카운팅 하는 과정을 단축 시켰다.
문제는 예제의 hello 와 hell에서 한번 더 누르게 하는 방법을 고민 했어야 했는데 트라이에 현재 위치에서 등록이 끝난 경우가 있는지를 판단해 있다면 한번 더 누르게 하는 방법으로 구현 했다.

삼성 B형을 준비하기위해 string없이 구성하려니 생각보다 더 오래 걸렸다.

알고리즘

1. 입력이 존재하는지 확인한다.
2. 입력이 존재 한다면 문자열 개수와, 문자열 n개를 입력 받는다.
3. 트라이를 생성하고, 트라이에 문자열을 추가한다.
   1. 문자열에서 현재 탐색중인 문자에 대하여 자식 노드가 없다면 자식 노드를 생성한다.
   2. 자식 노드로 이동한다.
   3. 문자가 널문자가 나올 때 까지 반복한다.
4. 각 문자에 대해서 탐색시간을 조사한다.
   1. 첫 문자는 무조건 눌러야 하므로 결과값의 초기 값을 1로 시작한다..
   2. 두번째 문자부터 자식노드의 개수가 2 이상이거나, 현재 위치에서 문자가 끝난 기록이 있다면 결과값을 1 증가시킨다.
   3. 다음 문자를 탐색하고, 탐색하는 노드를 자식 노드로 이동시킨다.
   4. 마지막 문자까지 탐색 후 결과값을 반환한다.
5. 모든 문자열에 대해서 각 값을 더하고, 문자열의 개수로 나눈다.
6. 소수점 2자리까지 반올림하여 출력한다.

소스코드

#include <iostream>

using namespace std;

const short charMAX = 80;
const int tcMAX = 100005;

struct myTrie {
	myTrie* child[26] = { nullptr, };
	int childCount = 0;
	bool wordExist = false;

	myTrie() {};
	~myTrie() { for (int i = 0; i < 26; i++) if (child[i] != nullptr) delete child[i]; }
};

struct myData {
	int count = 0;
	char inputs[tcMAX][charMAX + 1] = {};
};

void insertTrie(myTrie* root, char word[charMAX + 1])
{
	myTrie* cursor = root;
	for (int i = 0; word[i] != '\0'; i++) {
		if (cursor->child[word[i] - 'a'] == nullptr)
		{
			cursor->child[word[i] - 'a'] = new myTrie();
			cursor->childCount++;
		}

		cursor = cursor->child[word[i] - 'a'];
	}

	cursor->wordExist = true;
}

int countTrie(myTrie* root, char word[charMAX + 1]) {

	int count = 1;
	myTrie* cursor = root->child[word[0] - 'a'];
	int wordPos = 1;

	while (word[wordPos] != '\0' && cursor != nullptr)
	{
		if (cursor->childCount > 1 || cursor->wordExist)
			count++;
		cursor = cursor->child[word[wordPos] - 'a'];
		wordPos++;
	}

	return count;
}

double func(myData& md)
{
	double sum = 0;

	myTrie* root = new myTrie();

	for (int i = 0; i < md.count; i++)
		insertTrie(root, md.inputs[i]);

	for (int i = 0; i < md.count; i++)
	{
		int count = countTrie(root, md.inputs[i]);
		//cout << md.inputs[i] << " : " << count << '\n';
		sum += count;
	}

	delete root;

	return sum / md.count;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int count;

	while (cin >> count)
	{
		myData tcc;
		tcc.count = count;

		for (int i = 0; i < tcc.count; i++)
			cin >> tcc.inputs[i];

		double res = func(tcc);

		cout << fixed;
		cout.precision(2);

		cout << res << '\n';
	}

	return 0;
}

2019-04-15 19:00:03에 Tistory에서 작성되었습니다.