[C++] 2020 카카오 블라인드 가사 검색

접근 방법

---

 

효율성 또한 판별하는 문제 이므로 빠른 실행 시간이 요구되는 방법을 찾아야 했습니다.

 일단 쿼리의 수가 매우 많기 때문에 매번 새로운 계산을 한다기 보다 적절하게 값을 저장한 뒤에 불러와야 한다는 점과 트라이 구조를 사용하면 해결할 수 있을 것이라는 아이디어가 있었습니다.

 

트라이 구조의 한 노드는 아래와 같은 자료구조를 갖습니다.

typedef struct node{
    map <char, node> child; 
    map <int, int> info;
};

1. child는 현재 문자에 따라 child 노드로 연결 할 수 있는 링크입니다.

2. info는 현재 info[idx를 포함하여 단어가 끝나기 까지의 문자 길이] = 갯수 입니다.

 

info를 조금 더 자세히 설명하자면 아래의 그림과 같습니다.

1번 노드의 경우 현재 자신부터 말단 까지

길이가 4인 것의 갯수는 2개([1,2,3,4], [1,2,3,5]) 

길이가 3인 것의 갯수는 1개([1,2,6])

길이가 2인 것의 갯수는 1개([1,7])이다.

2번 노드의 경우 현재 자신부터 말단 까지

길이가 3인 것의 갯수는 2개 ([2,3,4], [2,3,5])

길이가 2인 것의 갯수는 1개 ([2,6])이다. 

 

 이러한 구조를 사용하는 이유는 query의 한 단어에서 '?'가 나왔을 때 모든 노드를 탐색하지 않고 ?의 갯수를 통해 바로 매치되는 단어의 수를 찾을 수 있기 때문입니다. 

 

 예를 들어 위와 같은 그림에서 단어가 "1???"라면 1노드 방문 후 2번 노드로 이동할 것이고 이 때의 문자는 ?이며 '?'의 수는 3개 이므로 2번 노드의 info[3]을 조회하면 바로 매치되는 단어의 수를 찾을 수 있습니다. 

 

 마지막으로 생각해야 하는 부분은 '?'가 앞에서 나오는 경우 입니다. 예를 들어 "??abc"와 같은 경우인데 이런 경우는 문자의 가장 뒤 부터 트라이를 탐색해야 합니다. 이 부분을 해결하기 위해서는 트라이를 구성할 때 역방향의 트라이 또한 만들어야 합니다. 예를 들어 "abcd", "def"이런 단어가 주어진다면 아래 그림과 같은 역방향의 트라이도 같이 만듭니다.

 

위의 설명을 이해했다면 문제는 크게 2가지 과정을 통해 해결할 수 있습니다.

1. words를 통해 정방향, 역방향 트라이 만들기

2. query의 '?'가 앞에서 시작한다면 역방향 트라이로 탐색, '?'가 뒤에서 시작한다면 정방향 트라이로 탐색

 

소스 코드

---

#include <string>
#include <vector>
#include <map>

using namespace std;

typedef struct node{
    map <char, node> child; 
    map <int, int> info; 
};

void insert(int idx, node &trie, string &word, int dir){
//dir == 1 정방향, dir == -1 역방향
    
    if (dir == 1 && idx == word.size()) 
		return;
    if (dir == -1 && idx == -1)
        return;
    
    int left = (dir == 1) ? word.size() - idx : idx + 1; //자신을 포함한 나머지 길이
    
    if(trie.info.count(left) == 0)
            trie.info.insert({left, 1});       
    else
        trie.info[left]++;
        
	if(trie.child.count(word[idx]) == 0)
        trie.child[word[idx]] = node();
    
	insert(idx + dir, trie.child[word[idx]], word, dir);
}

int querying(int idx, node &trie, string &word, int dir){
//dir == 1 정방향, dir == -1 역방향
    
    if(dir == 1 && idx == word.size())
        return 1;
    if(dir == -1 && idx == -1)
        return 1;
        
    // '?'가 나온 경우 3항연산자를 사용하여 남은 '?'의 갯수를 알아내어 매칭되는 단어의 수 탐색
    if(word[idx] == '?'){
        int cnt = (dir == 1) ? word.size() - idx : idx + 1; 
        return trie.info[cnt];
    }
    
    //매칭되는 단어가 있는 경우
    //정방향이라면 dir == 1 이므로 idx가 1 증가, 역방향은 dir == -1이므로 idx 1감소
    if(trie.child.count(word[idx]) > 0)
        return querying(idx + dir, trie.child[word[idx]], word, dir);
    
    //매칭되는 단어가 없는 경우
    return 0;
}

vector<int> solution(vector<string> words, vector<string> queries) {
    
    vector<int> answer;
    
    node f_trie;
    node r_trie;
    
    for(int i=0;i<words.size();i++){
        string word = words[i];
        insert(0, f_trie, word, 1); //정방향 트라이
        insert(word.size() - 1, r_trie, word, -1); //역방향 트라이
    }
    
    for(int i=0;i<queries.size();i++){
        
        string query = queries[i];
        int ret = 0;
        
        if(query[0] != '?') // 쿼리의 뒤쪽에 '?'가 있는 경우 
            ret = querying(0, f_trie, query, 1);
        else               // 퀴리의 앞에 '?'가 있는 경우
            ret = querying(query.size() - 1, r_trie, query, -1);
        
        answer.push_back(ret);
    }
    
    return answer;
}