가사검색
- 나의 풀이 1 (실패)
queries를 기준으로 트라이를 만들어 words를 순회하며 query에 해당하는 답의 갯수를 출력하는 풀이.
문제점
10,000개의 ?로 이루어진 쿼리를 끝까지 순회하며 확인해야 한다. ?로 이뤄진 부분은 접두사 접미사로 이루어져서 건너뛰기가 가능한데 queries를 기준으로 트라이를 만들어서 갯수를 세기위해 반드시 잎 노드까지 접근해야 했었다.
해결법
최대 글자수 만큼의 노드의 배열을 생성하고 해당하는 글자수의 노드에 queries가 아닌 words를 기준으로 트라이 자료구조를 만든다. 접두사 혹은 접미사가 반드시 연속된 ?임을 이용하여 접두사가 ? 이면 뒤집어진 query와 word를 이용해 순회하여 ? 부분을 적절히 건너뛰어 트라이의 탐색 속도를 올리는 것이 핵심이다.
#include <string>
#include <vector>
#include <iostream>
using namespace std;
struct Node {
char key;
bool isEnd;
vector<int> queryIdxs;
vector<Node*> childs;
Node(char _key, int _isEnd) : key(_key), isEnd(_isEnd) {}
};
void getAnswer(string& s, Node* n, int idx, vector<int>& answer) {
if (n == NULL) {
return;
}
if (idx == 0 && n->queryIdxs.size()) {
for(int stringIdx : n->queryIdxs) {
answer[stringIdx] += 1;
}
return;
}
if (s.size() == idx) {
if (n->isEnd) {
for (int stringIdx : n->queryIdxs) {
answer[stringIdx] += 1;
}
}
return;
}
for (auto ch : n->childs) {
if (ch->key == s[idx] || ch->key == '?') {
getAnswer(s, ch, idx + 1, answer);
}
}
}
bool isOnlyQm;
void makeNode(string& s, int idx, Node* root, int stringIdx) {
if (s[idx] != '?') {
isOnlyQm = false;
}
if (idx == s.size() - 1) {
for (auto rchd : root->childs) {
if (rchd->key == s[idx]) {
rchd->isEnd = true;
rchd->queryIdxs.push_back(stringIdx);
return;
}
}
Node* n = new Node(s[idx], true);
n->queryIdxs.push_back(stringIdx);
root->childs.push_back(n);
return;
}
for (auto rchd : root->childs) {
if (rchd->key == s[idx]) {
makeNode(s, idx + 1, rchd, stringIdx);
return;
}
}
Node* n = new Node(s[idx], false);
root->childs.push_back(n);
makeNode(s, idx + 1, n, stringIdx);
}
vector<int> solution(vector<string> words, vector<string> queries) {
vector<int> answer(queries.size(), 0);
vector<Node*> nodes(10001, NULL);
int queryIdx = 0;
for (string q : queries) {
isOnlyQm = true;
if (nodes[q.size()] == NULL) {
Node* root = new Node(NULL, false);
nodes[q.size()] = root;
makeNode(q, 0, nodes[q.size()], queryIdx);
if (isOnlyQm) {
nodes[q.size()]->queryIdxs.push_back(queryIdx);
}
}
else {
makeNode(q, 0, nodes[q.size()], queryIdx);
if (isOnlyQm && nodes[q.size()]->queryIdxs.size()) {
nodes[q.size()]->queryIdxs.push_back(queryIdx);
}
else {
nodes[q.size()]->queryIdxs.clear();
}
}
queryIdx += 1;
}
for (string word : words) {
getAnswer(word, nodes[word.size()], 0, answer);
}
return answer;
}
- 나의 풀이 2(성공)
정방향 순회는 iterator 역방향 순회는 reverse_iterator를 이용하여 순회하여 위의 해결방법으로 작성한 풀이. iterator객체는 잘 사용하면 정말 편리하다.
#include <iostream>
#include <string>
#include <vector>
constexpr int ALPHABETS = 26;
using namespace std;
struct Node {
bool isEnd;
int count;
Node* childs[ALPHABETS] = {
0,
};
Node() : isEnd(false), count(0) {}
};
void makeNode(Node* n, string::iterator it, string& s) {
n->count += 1;
if (it == s.end()) {
n->isEnd = true;
return;
}
int idx = *it - 'a';
if (n->childs[idx] == NULL) {
n->childs[idx] = new Node();
}
it++;
makeNode(n->childs[idx], it, s);
}
void makeRNode(Node* n, string::reverse_iterator rit, string& s) {
n->count += 1;
if (rit == s.rend()) {
n->isEnd = true;
return;
}
int idx = *rit - 'a';
if (n->childs[idx] == NULL) {
n->childs[idx] = new Node();
}
rit++;
makeRNode(n->childs[idx], rit, s);
}
int getMatchCount(Node* n, string& s, string::iterator it) {
if (*it == '?') {
return n->count;
}
int idx = *it - 'a';
it++;
if (n->childs[idx])
return getMatchCount(n->childs[idx], s, it);
else
return 0;
}
int getMatchCount(Node* n, string& s, string::reverse_iterator rit) {
if (*rit == '?') {
return n->count;
}
int idx = *rit - 'a';
rit++;
if (n->childs[idx])
return getMatchCount(n->childs[idx], s, rit);
else
return 0;
}
vector<int> solution(vector<string> words, vector<string> queries) {
vector<int> answer;
vector<Node*> nodes(10001, NULL), rnodes(10001, NULL);
for (string& s : words) {
Node*& n = nodes[s.size()];
Node*& rn = rnodes[s.size()];
if (n == NULL) {
n = new Node();
rn = new Node();
}
makeNode(n, s.begin(), s);
makeRNode(rn, s.rbegin(), s);
}
for (string& query : queries) {
if (rnodes[query.size()]) {
if (query[0] == '?') {
answer.push_back(getMatchCount(rnodes[query.size()], query, query.rbegin()));
} else {
answer.push_back(getMatchCount(nodes[query.size()], query, query.begin()));
}
} else {
answer.push_back(0);
}
}
return answer;
}
int main() {
vector<string> words = {"frodo", "front", "frost", "frozen", "frame", "kakao"};
vector<string> queries = {"fro??", "????o", "fr???", "fro???", "pro?", "?????", "asdfz"};
vector<int> ret = solution(words, queries);
for (int r : ret) {
cout << r << " ";
}
cout << "\n";
}
- 다른사람풀이 (이분탐색과 정렬)
먼저 역방향과 정방향으로 이뤄진 문자열 배열을 글자수를 기준으로 된 배열로 만들고, 해당하는 글자수의 배열을 방문하며 문자열을 정렬한다. query는 접두사가 ?이면 역방향 문자열 배열, 아니면 정방향 배열을 선택하고 query자신도 접두사면 뒤집고 아니면 정방향을 이용한다. query의 ?가 아닌 접두사 부분을 찾아내어 algorithm헤더의 lower_bound함수(이분탐색)를 이용해 query의 접두사와 같은 문자열의 시작 iterator와 끝나는 iterator를 찾아 둘의 차이를 반환하며 해당하는 문자열의 갯수가 나온다. 끝 iterator를 찾을 때 접두사.back()++를 하여 찾는다.
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
int solve(string& s, vector<string>& ar) {
if (s.front() == '?')
return ar.size();
string low, high;
for (char c : s) {
if (c == '?') {
high.back()++;
break;
} else {
low.push_back(c);
high.push_back(c);
}
}
auto l_index = lower_bound(ar.begin(), ar.end(), low);
auto h_index = lower_bound(ar.begin(), ar.end(), high);
return h_index - l_index;
}
vector<int> solution(vector<string> words, vector<string> queries) {
vector<int> answer;
vector<vector<string>> fr(10001);
vector<vector<string>> bk(10001);
for (string& s : words) {
fr[s.size()].push_back(s);
reverse(s.begin(), s.end());
bk[s.size()].push_back(s);
}
for (int i = 0; i < 10001; i++) {
sort(fr[i].begin(), fr[i].end());
sort(bk[i].begin(), bk[i].end());
}
for (string& s : queries) {
if (s.back() == '?') {
answer.push_back(solve(s, fr[s.size()]));
} else {
reverse(s.begin(), s.end());
answer.push_back(solve(s, bk[s.size()]));
}
}
return answer;
}
댓글남기기