Link https://www.acmicpc.net/problem/5670
소스결과 83284 KB / 596 ms
언어 C++ 17
출처 Baekjoon, Latin America Regional Contests 2012 C번
분류 트라이
설명
핸드폰의 자동 완성 기능과 비슷한 프로그램을 만들었을 때 평균 몇 회의 시도를 해야하는지 출력하자.
여러 문자열을 처리 해야하는 문제다.
앞서 풀었던 문제는 정적으로 처리 했던 것과는 다르게 동적 메모리가 필요하다.
트라이를 정적 메모리로 잡고 있기에는 메모리 낭비가 너무 심하다.
각 자리의 도메인이 소문자이기 때문에 트라이의 차수는 소문자 갯수인 26
사실 트라이를 구성 하는거 까지는 오래 안걸렸는데. 결과값으로 유도하기 위한 부분에서 생각이 좀 필요했다.
트라이의 멤버 변수에 childCount를 추가해 현재 자식의 개수가 몇개인지 기억 하도록 해 카운팅 하는 과정을 단축 시켰다.
문제는 예제의 hello 와 hell에서 한번 더 누르게 하는 방법을 고민 했어야 했는데 트라이에 현재 위치에서 등록이 끝난 경우가 있는지를 판단해 있다면 한번 더 누르게 하는 방법으로 구현 했다.
삼성 B형을 준비하기위해 string없이 구성하려니 생각보다 더 오래 걸렸다.
알고리즘
1. 입력이 존재하는지 확인한다.
2. 입력이 존재 한다면 문자열 개수와, 문자열 n개를 입력 받는다.
3. 트라이를 생성하고, 트라이에 문자열을 추가한다.
3-1. 문자열에서 현재 탐색중인 문자에 대하여 자식 노드가 없다면 자식 노드를 생성한다.
3-2. 자식 노드로 이동한다.
3-3. 문자가 널문자가 나올 때 까지 반복한다.
4. 각 문자에 대해서 탐색시간을 조사한다.
4-1. 첫 문자는 무조건 눌러야 하므로 결과값의 초기 값을 1로 시작한다..
4-2. 두번째 문자부터 자식노드의 개수가 2 이상이거나, 현재 위치에서 문자가 끝난 기록이 있다면 결과값을 1 증가시킨다.
4-3. 다음 문자를 탐색하고, 탐색하는 노드를 자식 노드로 이동시킨다.
4-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;
}