자동완성
Description
포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다! 단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다.
효과가 얼마나 좋을지 알고 싶은 라이언은 학습된 단어들을 찾을 때 몇 글자를 입력해야 하는지 궁금해졌다.
예를 들어, 학습된 단어들이 아래와 같을 때
go
gone
guild
go를 찾을 때 go를 모두 입력해야 한다.
gone을 찾을 때 gon 까지 입력해야 한다. (gon이 입력되기 전까지는 go 인지 gone인지 확신할 수 없다.)
guild를 찾을 때는 gu 까지만 입력하면 guild가 완성된다.
이 경우 총 입력해야 할 문자의 수는 7이다.
라이언을 도와 위와 같이 문자열이 입력으로 주어지면 학습을 시킨 후, 학습된 단어들을 순서대로 찾을 때 몇 개의 문자를 입력하면 되는지 계산하는 프로그램을 만들어보자.
Input
학습과 검색에 사용될 중복 없는 단어 N개가 주어진다.
모든 단어는 알파벳 소문자로 구성되며 단어의 수 N과 단어들의 길이의 총합 L의 범위는 다음과 같다.
2 <= N <= 100,000
2 <= L <= 1,000,000
Output
단어를 찾을 때 입력해야 할 총 문자수를 리턴한다.
Example
words result
[go,gone,guild] 7
[abc,def,ghi,jklm] 4
[word,war,warrior,world] 15
Code ( Time Limit Exceeded)
#include<bits/stdc++.h>
using namespace std;
int get_common_length(string str1, string str2){
int iter_length = min(str1.length(), str2.length());
int common_l = 0;
for(int i=0; i<iter_length; i++){
if(str1[i] == str2[i])
common_l++;
else
return common_l;
}
return common_l;
}
int solution(vector<string> words) {
int answer = 0;
vector<pair<string, int>> checked_words;
checked_words.clear();
checked_words.push_back(make_pair(words[0], 1));
// for (auto word : checked_words)
// cout << word.first << word.second<< endl;
for(int i = 1; i<words.size(); i++){
int val = 0;
for(int j = 0; j<checked_words.size(); j++)
{
// cout << "comparing word : " << word.first << "&" << word.second << endl;
int common_l = get_common_length(checked_words[j].first, words[i]);
// cout << "common Len : " << common_l << endl;
if (common_l == 0){
continue;
}
if (checked_words[j].second <= common_l){
if (checked_words[j].first.length() == common_l){
checked_words[j].second = common_l;
// cout << "word " << word.first << " : " << word.second << endl;
}
else
checked_words[j].second = common_l+1;
}
val = max(val, common_l);
}
if( words[i].length() > val)
val++;
checked_words.push_back((make_pair(words[i], val)));
}
for (auto word : checked_words)
answer += word.second;
return answer;
}Code (passed)
#include <bits/stdc++.h>
using namespace std;
struct Trie
{
int cnt;
bool leaf;
Trie* next[26];
Trie(){
cnt = 0;
leaf = false;
fill(next, next+26, nullptr);
}
void insert(const char* key){
if((*key)=='\0'){
cnt += 1;
leaf = true;
return;
} // basecase
int next_char_idx = *key - 'a';
if (next[next_char_idx] == nullptr){
next[next_char_idx] = new Trie();
}
cnt += 1;
next[next_char_idx]->insert(key + 1);
}
};
int find(Trie* trie, const char* word, int idx){
if ((*word) == '\0')
return idx;
if (trie->cnt==1)
return idx;
int next_char_idx = *word - 'a';
if(trie->next[next_char_idx])
return find(trie->next[next_char_idx], word+1, idx+1);
}
int solution(vector<string> words){
int answer = 0;
Trie* trie = new Trie();
for (string word : words){
trie->insert(word.c_str());
}
for (string word : words){
answer += find(trie, word.c_str(), 0);
}
return answer;
}Thoughts
이 문제는 2018 Kakao 블라인드 채용 3차의 마지막 문제로 정답률이 30%대를 기록한 어려운 문제이다.
처음 문제를 읽고 문제를 이해하는데는 그리 오랜 시간이 걸리지 않지만, 어떻게 풀어야할지 생각을 하는데 있어서 쉽게 정답이 원하는 방법을 생각해내지 못했고 결국에는 단순 naive한 중첩된 for 루프 밖에 떠오르지 않았다. O(n^2)의 시간 복잡도로 문제가 pass될거라고 처음에 믿지 않았지만 어쩔 수 없이 시도 했다.(내가 스스로 정해 놓은 시간은 한 시간 이었다) -> 결국 시간초과
이 문제를 풀기 위해서는 Trie 자료구조를 적용해야 한다.
Trie 자료구조는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다.
Trie를 사용하는 가장 큰 이유는 효율적인 문자열 탐색인데, 단순하게 모든 문자열을 하나씩 비교할 필요 없이 각 문자열의 문자를 트리 노드에 저장하여 트리 구조를 만들어 놓으면 빠르게 문자열을 탐색할 수 있다. 저장 공간의 크기가 커질 수 있는 단점은 있지만 검색어 자동완성, 사전에서 단어 찾기 같은 상황에서 효율적이다.
{bee, be, can, cat, cd} 문자열에 대한 trie 구조
이런 구조를 생각하면서 다시 이 문제를 어떻게 풀 것인지, 생각을 하면
우선, 언제 문자열을 그만 입력해도 자동완성이 될 것인가 다시 생각해 봤다.
입력하는 문자와 더이상 겹치지 않은 한마디로 그 노드의 카운트 값이 1인 순간 더 이상 탐색을 하지 않아도 되는 것이다.
또한, 마지막 leaf 노드에 도달하면 단어를 다 입력한 것이고 한마디로 그 단어는 다입력해야만 하는 경우이다.
그 후로는 단순히 프로그래밍이다.
이제 점점 cpp 문법이 다시 익숙해 지고 있긴 하나, struct나 class 를 자주 쓰지 않으면 문법과 익숙함이 떨어진다..
정리하자면,
매우 어려운 문제다. 실전에서 만나면 결코 쉽게 풀지 못하는 수준이나, 결과적으로는 자료구조이다.
문제를 읽고 어떤 자료구조를 이용하고, 어떤 로직을 짤지 생각만 할 수 있다면, 절대 못 풀 문제는 아니다.
