2020 KAKAO BLIND RECRUITMENT - 가사 검색

2020 KAKAO BLIND RECRUITMENT - 가사 검색

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

* 2가지 풀이법에 대한 후기 입니다.

1. 효율성을 고려하지 않은 풀이
2. 기존 정답 방식과 조금 다르지만 성공한 풀이

1. 효율성을 고려하지 않은 풀이

문제를 보자마자 작성한 풀이법 입니다.
카카오 문제는 정확성만을 테스트 하는 문제 / 정확성과 효율성 모두를 고려해야 하는 문제로 나뉘는데,
전자의 경우 정답을 맞추고 기본 자원 제한 사항을 통과하면 정답으로 인정됩니다.
문제는 후자 스타일의 문제인데, 정확하게 정답을 맞춰도 시간,자원 등 효율성을 고려하지 않고 풀면 가차없이 실패로 뜹니다.

이 문제 또한 효율성을 고려해야 하는 문제인데, 정확성만 고려하더라도 100점은 아니지만 일부점수를 얻어 갈 수 있기 때문에 일단 정확성을 위주로 풀어보았습니다.

특별한 자료구조나 알고리즘을 사용하지 않아도 누구나 떠올릴 수 있는 '쿼리와 워드를 모두 1:1비교하는 방식' 입니다.

만약 '?'라면 워드에 어떤 문자가 와도 괜찮으므로 continue시키고, 그렇지 않으면 일치도만 보면 됩니다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer;
    bool isCorrect;
    
    
    for(int i = 0 ; i < queries.size(); i++){
        answer.push_back(0);
        for(int j = 0 ; j < words.size(); j++){
            if (queries[i].length() != words[j].length()) {
                continue;
            }
            isCorrect = true;
            for(int c = 0; c < queries[i].size(); c++){
                if (queries[i][c] == '?') {
                    continue;
                }else if(queries[i][c] != words[j][c]){
                    isCorrect = false;
                    break;
                }
                
            }
            if(isCorrect) answer[i]++;
        }
        
    }
    return answer;
}

하지만 이런 풀이로는 정확성 25.0 / 효율성 30.0 / 합계 55.0 이라는 점수밖에 얻을 수 없었습니다.(효율성 테스트 1,2,3 시간초과)

그래서 효율성을 고려한 풀이를 생각해 봤습니다.

2. 기존 정답 방식과 조금 다르지만 성공한 풀이

일단 Trie구조를 사용해야 한다는 것은 알았습니다. 하지만 조금 상황에 맞게 바꿔야 했고 가장 중요한것은 '무엇으로' Trie tree를 구성해야 하는것인가 하는 문제였습니다.

결론부터 보면 카카오 테크 블로그에 있는 해설이나, 다른분들의 정답을 보면 모두 검색단어(워드)를 Trie에 넣고, 물음표가 접두사에 있거나 접미사에 있을수 있기 때문에 단어의 앞에서부터 만든 트리 하나, 뒤에서부터 만든 트리 하나 , 이렇게 2개의 트리를 만드는 방식이었습니다.

처음에 뒤에서부터 보는 트리를 하나 더 만들 생각을 하지못하여 , 쿼리로 Trie를 만들어야겠다 라고 생각했습니다. 여기서부터 고생길 이였습니다.

구조는 그렇게 복잡하지 않았습니다. 쿼리를 Trie에 넣고, 워드로 이 트리를 순회하는데, 총 2가지 방향으로 항상 진행했습니다.

현재 검사해야될 단어, 그리고 '?' 라는 2가지 방향으로 탐색한다면 최종적으로 그 워드가 걸릴 수 있는 모든 쿼리노드에 도달하게 됩니다.

하지만 아무리 최적화를 해도 계속 segmentation fault(core dumped)가 발생하였고 , 이 방식으로는 풀수 없는 것인가 고민하게 되었습니다.

결론적으로 아무리 최적화를 하여도 기존 방식보다 많은 재귀를 돈다는 것을 확인하였습니다.

워드로 Trie를 구성하는 기존 방식은 쿼리에서 ?가 나오면 탐색을 멈추고 자식 노드 중에서 쿼리와 길이가 동일한 자식 노드의 숫자만 세면 되지만, 위 방법에서는 그런거 없이 무조건 끝까지 내려가야 한다는 점 이었습니다.

만약 10,000의 길이를 가진 쿼리가 100,000개 있다면 워드마다 해당되는 쿼리를 찾을 때 마다 최대 10,000깊이의 재귀를 돌아야 하며 이를 반복한다고 생각하면 메모리 초과는 당연했습니다.

결국 쿼리에서 ?가 등장하면 재귀를 돌지않고 ?가 등장하지 않거나, 리프노드에 도달할때 까지 반복문을 돌게 해서 해결했습니다.

그래도 다시 풀면 ... 그냥 워드로 Trie2개 만들것같아요 ㅠ
성공한 코드 전문입니다.

#include <string>
#include <vector>
#include <algorithm>
#include <string.h>


using namespace std;

vector<int> answer;

int n = 0;
vector<int> solution(vector<string> words, vector<string> queries);
struct Trie {
    bool isWord;
    int num;
    Trie* next[27];
    
    Trie(): isWord(false) , num(-1){
        memset(next,0,sizeof(next));
    }
    ~Trie(){
            for(int i=0;i<27;i++){
                if(next[i])
                    delete next[i];
            }
        }
    
    void insert(const char* key){
        if ((*key) == '\0') {
            isWord = true;
            if (num != -1) {
                answer[n] = -(num+1);
            }
            else num = n;
            return;
        }
        if ((*key) == '?') {
            if (next[26] == NULL) {
                next[26] = new Trie();
            }
            next[26]->insert(key+1);
        }else{
            int curr = (*key)-'a';
            if (next[curr] == NULL) {
                next[curr] = new Trie();
            }
            next[curr]->insert(key+1);
        }
    }
    void find(const char* word){
        
        if (isWord) {
            if (*(word) == '\0') {
                answer[num]++;
                return;
            }
        }
        int curr;
        curr = *(word)-'a';
        
        if (next[curr] != NULL) {
            next[curr]->find(word+1);
        }
        
        if (next[26]!=NULL) {
            Trie* temp = next[26];
            while (temp->next[26] != NULL) {
                word++;
                if (temp->next[(*word)-'a'] != NULL) {
                    temp->next[(*word)-'a']->find(word+1);
                }
                temp = temp->next[26];
                
            }
            
            temp->find(word+1);
        }
        
        
    }
};

Trie* tree[10001];


vector<int> solution(vector<string> words, vector<string> queries) {
    
    
    
    for(int i = 0 ; i < queries.size(); i++){
        answer.push_back(0);
        if(tree[queries[i].size()] == NULL) tree[queries[i].size()] = new Trie();
        const char* temp = queries[i].c_str();
        tree[queries[i].size()]->insert(temp);
        n++;
    }
    
    for(int i = 0 ; i < words.size(); i++){
        if(tree[words[i].size()] == NULL) continue;
        const char* temp = words[i].c_str();
        tree[words[i].size()]->find(temp);
    }
    
    for(int i = 0 ; i < answer.size(); i++){
        if(answer[i] < 0 ){
            answer[i] = answer[(-answer[i])-1];
        }
    }
    
    
    return answer;
}

후기

사용하지 않아도 되는 조건은 없는걸 다시 한번 알았습니다.
수학 과외 할때 학생들한테 항상 주어진 조건중에 안쓰거나 만족하지 못한 조건이 있으면 답이 맞아도 틀린것이다 라고 얘기했었는데 정작 제가 안지키고 있었습니다.
물음표는 앞이나 뒤에만 올수있고, 없거나 중간에 올수 없다라는 조건을 등한시해서 풀이가 오래걸렸습니다.