[프로그래머스/C++] 가사 검색 (2020 KAKAO BLIND RECRUITMENT)

문제

문제 설명

 

 

풀이

 

처음 이 문제를 봤을 때 trie 알고리즘을 사용하면 빨리 문제를 해결할 수 있겠다는 생각이 들었다.

왜냐하면 특정 문자가 같은지 비교하고 수를 세는 과정에서 trie 알고리즘을 사용하면 빠르게 해결 될 것 같았기 때문이다.

 

문제는 조건을 제대로 안읽어서 ab?cd와 같이 중간에 ?가 들어갈 수 있는 줄 알고 코드를 구현했다.

 

하지만 알고보니 양 끝에만 ?가 연속적으로 들어갈 수 있었다...

 

[문제 풀이]

 

trie 알고리즘으로 문제를 푼 방법은 다음과 같다.

 

예를 들어 trie라는 문자가 들어온다고 가정하자.

이 경우 위 그림과 같이 t 뒤에는 물음표가 3개 오는 경우가 올 수 있다.

이를 map<int, int>를 이용해 [문자열의 길이: 개수]로 저장해두면 빠르게 찾아서 return할 수 있다.

만약 queries에 t???라는 문자를 찾는다고 생각해 보자.

그러면 ?가 나올경우 그 뒤에 있는 모든 문자열은 ?이기 때문에 find를 멈추고, map에 저장된 값을 즉시 반환하면 된다.

tre라는 문자가 새로 들어올 경우

마찬가지로 tre라는 문자가 들어오면 size를 계산해 map에 개수를 추가하면 된다.

 

 

 

여기서 문제가 생기는데 ???e라는 문자가 들어오는 경우에는 ???e를 찾아야 하는데 ????의 수를 반환하게 되는 문제가 생길 수 있다.

 

그러므로 이 문제를 해결하기 위해 역방향 단어를 저장할 trie 구조를 하나 더 만들어 eirt라는 단어를 저장한다.

 

이후후 queries에 맨 앞 문자가 ?라면 ????ab 형태이므로 ba????라는 단어를 역방향 단어를 저장한 trie에서 단어를 찾는다.

만약 맨 앞 문자가 ?가 아니라면 ab??? 형태이므로 순방향 단어를 저장한 trie에서 ab???라는 단어를 찾으면 된다.

 

 

 + trie 구조에 map을 추가해 문제를 풀었더니 단순히 map을 이용해 문제를 풀 수 있겠다는 생각이 들었다.

예를 들어 abcde라는 문자가 들어온다면 abcd?, abc??, ab???, a????, ?????, ????e, ???de, ??cde, ?bcde 를 map에 추가하고 queries에서 찾으면 된다. 

 

실제로 이런 식으로 map에서 찾아 구현한 코드가 있었다.

 

하지만 단순히 구현할 경우 효율성에서 시간 초과가 났다. 

 

map으로 문제를 풀기 위해서는 반대로 queries에서 찾을 단어를 먼저 추가하고, 문자의 형태가 queries에서 원하는 형태라면 개수를 +1 하도록 코드를 구현하면 통과가 된다.

 

 

+ 다른 사람이 trie구조로 문제를 푼 방법을 봤는데, 굳이 역으로 trie를 탐색하지 않아도 해결할 수 있었다.

 

반대로 queries에 있는 단어를 먼저 trie에 넣고, word의 단어가 queries에서 원하는 단어와 같은지 찾으면 된다.

이렇게 계산하면, 쓸데없는 반복이 없이 queries에서 원하는 단어를 빠르게 찾을 수 있다.

trie에 없는 단어라면 queries에서 찾는 단어가 아니기 때문에 빠르게 가지치기를 할 수 있기 때문

 

 

​

[아이디어 정리]

1. trie 구조를 이용해 단어의 개수를 빨리 return할 수 있도록 한다.
2. 단어에 ?가 포함되어 있으므로, trie에 단어를 넣을 때마다 단어의 size와 map을 이용해 ?가 뒤에 몇 개 포함된 경우가 있는지 저장해 둔다.
3. queries의 단어를 find하다가 ?가 나오면 그 뒤에 나오는 문자는 전부 ?이므로, map에서 뒤에 ?가 나올 수 있는 경우를 return한다.
4. 단어가 ???ab일 경우는 ba???와 같이 뒤집어서 탐색할 수 있도록, 역방향 단어를 저장할 trie를 하나 더 만들어 문제를 푼다.

 

 

 

Code

 

 

#include <string>
#include <vector>
#include <iostream>
#include <map>
using namespace std;

struct Trie{
    int cnt; // 이 문자가 마지막인 문자의 cnt;
    Trie* children[26];
    map<int,int> qMap;//특정 사이즈가 있다면 반환
    //생성자
    Trie(){ 
        cnt=0;
        for (int i=0; i<26; i++)
            children[i]=NULL;        
    }
    
    ~Trie(){ //소멸자
        for (int i=0; i<26; i++)
        {
            if (children[i])
                delete children[i];            
        }
    }
    
    void insert(const char* s, int stringSize)
    {
        if (*s=='\0') //마지막 문자였다면
        {
            cnt+=1;
            return;
        }
        int idx=*s-'a';
        if (children[idx]==NULL)
        {
            children[idx]=new Trie;
        }
        children[idx]->insert(s+1,stringSize-1);
        qMap[stringSize]+=1;
    }
    
    int find(const char* s, int stringSize)
    {
        if (*s=='\0')
        {
           return this->cnt;
        }
        if (*s=='?')
        {
            return qMap[stringSize];
        }
        else
        {
            int idx=*s-'a';
            if (children[idx]==NULL)
            {
                return 0;
            }
            return children[idx]->find(s+1,stringSize-1);
        }
    }
};


vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer(queries.size(),0);
    Trie *trieStruct=new Trie();
    Trie *revTrieStruct=new Trie();
    for (int i=0; i<words.size(); i++)
    {
        trieStruct->insert(words[i].c_str(),words[i].length());
        string ttt="";
        for (int j=0; j<words[i].length(); j++)
        {
            ttt=words[i][j]+ttt;
        }
        revTrieStruct->insert(ttt.c_str(),ttt.length());
    }
    int ans=0;
    for (int i=0; i<queries.size(); i++)
    {
        if (queries[i][0]=='?')
        {
            string ttt="";
            for (int j=0; j<queries[i].length(); j++)
            {
                ttt=queries[i][j]+ttt;
            }
            answer[i]=revTrieStruct->find(ttt.c_str(),ttt.length());    
        }
        else
        {
            answer[i]=trieStruct->find(queries[i].c_str(),queries[i].length());            
        }
    }
    return answer;
}

 

 

 

Code (단순 Map풀이)

 

 

#include <string>
#include <vector>
#include <iostream>
#include <set>
#include <unordered_map>
using namespace std;

vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer(queries.size(),0);
    unordered_map<string,int> qmap;
    set<string> ss;
    for (int i=0; i<queries.size(); i++)
    {
        ss.insert(queries[i]);
    }
    for (int i=0; i<words.size(); i++)
    {
        string str1=words[i],str2=words[i];
        
        for (int j=0; j<words[i].length()-1; j++)
        {
            str1[j]='?',str2[words[i].length()-1-j]='?';
            if (ss.find(str1)!=ss.end())
                qmap[str1]+=1;
            if (ss.find(str2)!=ss.end())
                qmap[str2]+=1;
        }
        str1[words[i].length()-1]='?';
        if (ss.find(str1)!=ss.end())
            qmap[str1]+=1;
    }
    for (int i=0; i<queries.size(); i++)
        answer[i]=qmap[queries[i]];
    return answer;
}

 

---

처음에 문제를 잘못 읽어서 푸는데 오래 걸릴 뻔 했다...

문제를 풀고 난 뒤에도 이렇게 푸는게 효율적일까 의문이 들어서 다른 사람들의 코드를 보는데 더 효율적인 방법이 있었다.

word를 기준으로 trie 구조를 만들고 삽입하는 것 보다, queries를 기준으로 trie 구조를 만들고 삽입하는 방법이 더 효율적이었다.

처음에 26알파벳에 ?를 추가해 27자를 사용하는 건 어떨까 생각을 했었는데, words에 있는 단어를 ?에 계속 추가하면 2^n와 같은 시간복잡도가 돼서 다른 방법을 생각했다.

다시 생각해보니 queries를 기준으로 ?를 추가해 사용하면 되는데, 풀 때는 왜 안떠올랐을까;;

프로그래머스