2020 Kakao blind 60060 - 가사검색(이분탐색, 트라이 자료구조) c++

- 쿼리 벡터의 단어(와일드카드가 섞여있는)에 대해서 words벡터에서 일치할 수 있는 단어가 몇 개인지 리턴하는 로직을 만드는 문제이다.

- 일단  words 벡터와 queries벡터의 길이가 각각 10만이므로 2중 for문으로 탐색하는 O(N^2) = 100억 로직으로 풀 수 없다.
따라서 검색로직의 파라미터가 되는 쿼리에 대한 접근은 줄일 수가 없으니까 words 벡터를 탐색시에 logn 이하의 로직을 써서 NlogN이하의 복잡도 알고리즘을 사용해야한다. 그러므로 이분탐색이 적절하다고 생각하고 접근하였다. (대신 연속된 문자열을 키로 사용해서 빠른 조회가 가능한 트라이 자료구조를 사용할 수 있다. 여기서 문자열이 시작되는 s[0]을 루트노드로 하여 조합가능한 모든 문자열에 대해서 트리구조로 노드를 만들어서 조회하는 방식이다. 이 문제에서는 소문자 알파벳 문자열만을 사용하므로 a~z로 시작하는 길이 26의 트라이 배열을 선언해서 모든 words를 저장한 뒤 탐색하는 방식을 생각해 볼 수 있다. 

- 이분탐색을 이용한다면 words를 길이순, 길이가 같다면 사전순(ascii순)으로 정렬한다. 이 때 처음부터 와일드카드가 나오는 경우, 뒤에서 와일드카드가 나오는 문자를 구분하되 로직을 똑같이 쓰기 위해서 뒤집힌 단어를 담는 words배열, 원래 배열을 따로 사용해서 소팅을 해준다. 

- 탐색할 쿼리값에 와일드카드가 있는 경우 (xy???) 사전순으로 정렬한다고 했을 때 인덱스가 가장 작은 하한값은 "xyaaa" 일것이고, 가장 큰 상한값은 "xyzzz" 일 것이다. lower_bound, upper_bound를 통해서 words벡터 상에서 상한, 하한을 구한 뒤 빼면 그 범위 내에서 쿼리조건에 해당되는 값들의 갯수가 나온다. 역순으로 나오는 경우에 대해서도 뒤집은 단어들의 벡터에서 각각 상,하한을 구한 뒤 빼주면 된다.

• k의 상한의 위치 - k의 하한의 위치 = k의 갯수
• lower_bound와 upper_bound의 위치가 같으면 그 수는 없음(0개)

// 1. 이분탐색
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

bool cmp(const string& a, const string& b) {
    if (a.length() == b.length()) return a < b;
    return a.length() < b.length();
}

// 찾고자 하는 키워드queires 10만, 모든 단어 담긴 배열 words 10만
vector<int> solution(vector<string> words, vector<string> queries) {
    int N = queries.size();
    vector<int> answer(N);

    vector<string> rwords = words;
    sort(words.begin(), words.end(), cmp);
    for (string& s : rwords) {
        reverse(s.begin(), s.end());
    }
    sort(rwords.begin(), rwords.end(), cmp);

    // words {"frodo", "front", "frost", "frozen", "frame", "kakao"};
    // queries {"pro?", "????o", "fr???", "fro??", "fro???"}

    for (int i = 0; i < queries.size(); ++i) {  // ? 63, a 97 z 122
        if (queries[i][0] != '?') {             // ?로 끝남
            string lquery = queries[i], rquery = queries[i];
            for (char& ch : lquery) {
                if (ch == '?') ch = 'a';
            }  // fraaa
            for (char& ch : rquery) {
                if (ch == '?') ch = 'z';
            }  // frzzz

            // 오름차순 정렬에서 특정범위 속하는 숫자가 몇개 있는지, k상한 - k하한 = k갯수
            auto lIt = lower_bound(words.begin(), words.end(), lquery, cmp);  // fraaa 하한위치
            auto rIt = upper_bound(words.begin(), words.end(), rquery, cmp);  // frzzz 상한위치
            answer[i] = rIt - lIt;
        } else {  // ?로 시작함
            reverse(queries[i].begin(), queries[i].end());
            string lquery = queries[i], rquery = queries[i];
            for (char& ch : lquery) {
                if (ch == '?') ch = 'a';
            }  // aaaao -> oaaaa
            for (char& ch : rquery) {
                if (ch == '?') ch = 'z';
            }  // zzzzo -> ozzzz

            auto lIt = lower_bound(rwords.begin(), rwords.end(), lquery, cmp);
            auto rIt = upper_bound(rwords.begin(), rwords.end(), rquery, cmp);
            answer[i] = rIt - lIt;
        }
    }

    return answer;
}

// 2. 트라이 자료구조
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

const int ALPHABET_SIZE = 26;

struct TrieNode {
    vector<TrieNode*> children;
    int count;

    TrieNode() : children(ALPHABET_SIZE), count(0) {
    }

    void insert(string& s) {
        TrieNode* curr = this;
        for (char& ch : s) {
            curr->count++;
            int next = ch - 'a';
            if (curr->children[next] == nullptr) {
                curr->children[next] = new TrieNode();
            }

            curr = curr->children[next];
        }

        curr->count++;
    }

    int search(string& s) {
        TrieNode* curr = this;
        int count = 0;
        for (char& ch : s) {
            if (ch == '?') {
                count = curr->count;
                break;
            }

            curr = curr->children[ch - 'a'];
            if (curr == nullptr) {
                break;
            }
        }

        return count;
    }
};

vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer;

    TrieNode TrieRoot[10001];
    TrieNode ReverseTrieRoot[10001];

    for (string& w : words) {
        int len = w.length();
        TrieRoot[len - 1].insert(w);
        reverse(w.begin(), w.end());
        ReverseTrieRoot[len - 1].insert(w);
    }

    for (string& q : queries) {
        int ans;
        int len = q.length();
        if (q[0] == '?') {
            reverse(q.begin(), q.end());
            ans = ReverseTrieRoot[len - 1].search(q);
        } else {
            ans = TrieRoot[len - 1].search(q);
        }
        answer.push_back(ans);
    }

    return answer;
}

https://programmers.co.kr/learn/courses/30/lessons/60060

코딩테스트 연습 - 가사 검색