[2020 KAKAO BLIND RECRUITMENT] 가사 검색
[링크] https://programmers.co.kr/learn/courses/30/lessons/60060
💎 문제 조건과 설명
문제 조건과 설명은 위의 링크를 참조 부탁드립니다.
🚀 생각한 아이디어
words 배열에 “frodo”, “front”, “frost”, ‘frozen”, “frame”, “kakao” 가 있다고 가정해 보겠습니다.
그리고 찾고자 하는 키워드 queries 배열에는 "fro??", "????o", “fr???”, “fro???”, “pro?” 가 있습니다.
"fro??" 를 words 배열에서 찾는다는 의미는, words 배열에서 “froaa” 보다 크거나 같고 “frozz” 보다 작거나 같은 것의 갯수를 세면 됩니다.
즉, words 배열에서 ⭐“froaa” 이상인 값이 처음으로 나오는 인덱스를 구하고, ⭐“frozz”을 초과하는 값이 처음으로 나오는 인덱스를 구한 다음 두 인덱스의 차이를 구하면 갯수가 됩니다.
이 때 ⭐은 C++에서 각각 lower_bound, upper_bound 함수로 구할 수 있습니다. 이 두 함수는 내부적으로 이진 탐색 알고리즘을 사용하여 탐색합니다.
"????o" 를 words 배열에서 찾으려면 어떻게 해야 할까요? 앞에서처럼 aaaao ~ zzzzo 라고 생각하고 탐색하면 성립이 안 됩니다. 맨 끝이 무조건 o로 끝나는 것만 찾아야 하기 때문입니다. 이처럼 ?가 앞에서부터 붙었을 경우 이를 거꾸로 뒤집어서 탐색하면 됩니다.
즉, "????o" 를 "o????" 로 뒤집고, words 배열도 전부 거꾸로 뒤집어 놓습니다. -> “odorf”, “tnorf”, “tsorf”, “nezorf”, “emarf”, “oakak”
그 다음 뒤집힌 words 배열에서 “o????” 를 대입하여 찾습니다. “oaaaa” ~ “ozzzz” 인 것의 갯수를 찾으면 됩니다. 방법은 위에서 말했던 것과 동일하며, 찾으려는 단어를 뒤집고, words 배열을 거꾸로 뒤집은 것에서 찾는다는 것만 다릅니다.
만약 queries 배열 원소 하나씩 words 배열에서 선형 탐색으로 앞에서부터 차례대로 살펴보는 식으로 짠다면 시간초과가 발생할 것입니다.
하지만 위의 방법을 사용할 경우 이진 탐색 알고리즘은 시간복잡도가 logN 이므로 시간 초과 걱정 없이 코드를 작성할 수 있습니다!
lower, upper_bound 설명 바로가기 : (링크 클릭)
- 소스코드 : 위에서 했던 설명을 그대로 코드로 작성하였습니다.
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
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
// C++용 replace_all 함수. str에서 pattern을 replace로 일괄적으로 변경한다.
string replace_all(const std::string& str, const std::string& pattern, const std::string& replace) {
string result = str;
string::size_type pos = 0;
string::size_type offset = 0;
while ((pos = result.find(pattern, offset)) != std::string::npos)
{
result.replace(result.begin() + pos, result.begin() + pos + pattern.size(), replace);
offset = pos + replace.size();
}
return result;
}
// lower, upper_bound를 활용하여 갯수를 세는 함수
int cnt_value(vector<string>& v, string leftVal, string rightVal) {
vector<string>::iterator rightIndex = upper_bound(v.begin(), v.end(), rightVal);
vector<string>::iterator leftIndex = lower_bound(v.begin(), v.end(), leftVal);
return rightIndex - leftIndex;
}
vector<int> solution(vector<string> words, vector<string> queries) {
vector<int> answer;
vector<vector<string>> origin_words;
vector<vector<string>> reversed_words;
origin_words.resize(10001);
reversed_words.resize(10001);
for (int i = 0; i < words.size(); i++) {
int size = words[i].size();
origin_words[size].push_back(words[i]);
reverse(words[i].begin(), words[i].end());
reversed_words[size].push_back(words[i]);
}
// lower, upper_bound를 사용하려면 오름차순 정렬이 되어 있어야 합니다.
for (int i = 0; i < 10001; i++) {
if (origin_words[i].size() == 0) continue;
sort(origin_words[i].begin(), origin_words[i].end());
sort(reversed_words[i].begin(), reversed_words[i].end());
}
for (int k = 0; k < queries.size(); k++) {
int cnt = 0;
string target = queries[k];
int targetSize = target.size();
if (target[0] != '?') {
cnt = cnt_value(origin_words[targetSize], replace_all(target, "?", "a"), replace_all(target, "?", "z"));
answer.push_back(cnt);
}
else {
reverse(target.begin(), target.end()); // 찾고자 하는 값 뒤집고, 밑에서는 뒤집힌 words 배열에서 찾기
cnt = cnt_value(reversed_words[targetSize], replace_all(target, "?", "a"), replace_all(target, "?", "z"));
answer.push_back(cnt);
}
}
return answer;
}