2021. 2. 10. 21:10ㆍ카테고리 없음
1. 트라이 구현
문제를 해결 할 자료구조는 '트라이'다.
트라이는 문자열을 찾는데에 있어서 효율적인 자료구조이다.
주어진 단어들의 빈도에따라 추천하는 단어가 달라지므로
트라이를 구현할 때 각 노드마다
단어장에서 추천하는 단어의 인덱스변수와
추천하는 단어를 갱신하기 위한 우선순위 변수 두개가 필요하다.
단어장의 단어들을 트라이에 삽입할 때
'사전순'으로 추천하므로 일단 먼저 단어장을 정렬해야한다.
정렬한뒤 우선순위가 큰 것으로 업데이트 시켜주면 트라이 단어장은 완성된다.
2. 검색 구현
트라이에서 문자열 s 를 검색할때
s가 없으면 s의 사이즈를 반환하고,
s가 해당 노드에서 추천하는 문자열과 같으면 탭을 눌러
이때까지 타자친 횟수에 1을 더해 값을 반환한다.
그 외의 경우는 문자열을 끝까지 친 경우이므로 타자친 횟루를 반환하면된다.
여기서 중요한것은 추천하는 문자열과 검색하고 있는 문자열의 비교이다.
각 노드를 움직일때마다 비교를 하게되면 시간이 오래걸리므로 이전 추천과 현재 추천이 다를 때에만
비교하도록 구현하였다.
3. 시간 복잡도
전체 코드의 주요 동작들을 살펴보자
1. dic 정렬
2. trie 생성
3. search
1번 정렬의 시간 복잡도는 O(KNlgN) 의 시간 복잡도를 가진다
(문자열 정렬이므로 문자열 길이 평균이 K라고 하면)
trie의 생성에서
일단 N개의 문자들을 insert하므로 단어의 길이가 k라고하면
O(Nk) 의 시간이 걸린다.
search에서
문자열의 길이 단어의 개수 M 단어의 길이 K , 단어를 비교할때 K
O(M*K*K) 의 시간 복잡도를 가진다.( 단어를 비교하는 상황은 적으므로 시간안에 수행 가능하다)
만약 단어를 비교하지 않고 find함수를 사용하여 미리 trie에 있는지 없는지 파악하면
인덱스 비교만으로 단어 비교 없이 search할 수 있다.
그러면 한 단어의 타이핑 횟수를 찾는데에 단어의 길이 k 만큼만 걸리므로
총 수행시간은 O(KNlgN + NK + M*K) 이다. 여기서 N*K 는 사전 전체의 길이 , M*k는 타이핑할 문자열의 길이 이므로
모든 문자열의 길이의 합을 L 이라하면 O(KNlgN + L) 이라고 표현할 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
using namespace std;
int toNumber(char ch) {
return ch - 'A';
}
pair<string, int> dic[10000];
string words[20000];
struct trieNode {
int terminal;
int priority;
int recommend;
trieNode* alphabet[26];
trieNode(): recommend(-1), priority(0), terminal(-1) {
for(int i = 0 ; i < 26 ; i++)
alphabet[i] = NULL;
}
~trieNode() {
for(int i = 0; i < 26; i++)
delete alphabet[i];
}
void insert(const string& str, int index, int priority) {
const char* ch = str.c_str();
trieNode* node = this;
while(*ch != '\0') {
if(node->alphabet[toNumber(*ch)] == NULL) {
node->alphabet[toNumber(*ch)] = new trieNode();
}
if(node->alphabet[toNumber(*ch)]->priority < priority) {
node->alphabet[toNumber(*ch)]->priority = priority;
node->alphabet[toNumber(*ch)]->recommend = index;
}
node = node->alphabet[toNumber(*ch)];
ch++;
}
node->terminal = index;
}
};
int search(trieNode* trie, const string& str) {
const char* ch = str.c_str();
int ret = 0;
int recommend = -1;
int beforeRecommend = -1;
while(*ch != '\0') {
ret++;
if(trie->alphabet[toNumber(*ch)] == NULL) {
//cout<<" return "<<str.size()<< "\n";
return str.size();
}
recommend = trie->alphabet[toNumber(*ch)]->recommend;
if(*(ch+1) != '\0' && beforeRecommend != recommend && dic[recommend].first == str) {
ret++;
break;
}
trie = trie->alphabet[toNumber(*ch)];
ch++;
beforeRecommend = recommend;
}
//cout<<" return "<<ret<<"\n";
return ret;
}
int C;
int N;
int M;
void initial(trieNode* trie) {
for(int i = 0 ; i < N; i++) {
//cout<<"ini: "<<i<<"\n";
trie->insert(dic[i].first, i, dic[i].second);
}
}
int minTyping() {
trieNode* trie = new trieNode();
initial(trie);
int ret = 0;
for(int i = 0; i < M; i++) {
//cout<<"index: "<<i<<"\n";
ret+= search(trie, words[i]);
}
return ret + M-1;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin>>C;
for(int i = 0; i < C; i++) {
cin>>N>>M;
for(int j = 0; j < N; j++) {
cin>>dic[j].first>>dic[j].second;
}
sort(dic, dic+N);
for(int j = 0; j < M; j++) {
cin>>words[j];
}
cout<<minTyping()<<"\n";
}
}
|
cs |