[ 프로그래머스 가사검색 (Lv4) ] (C++)

프로그래머스의 가사검색(Lv4) 문제이다.

[ 문제풀이 ]

가사가 주어지고, 검색키워드가 주어졌을 때, 해당 검색 키워드로 몇 개의 가사를 찾을 수 있는지 구해야 하는 문제이다.

본인은 자료구조 'Trie(트라이)'를 이용해서 접근해 보았다.

먼저 구체적인 풀이를 알아보기 전에, 트라이에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ 자료구조 TRIE 알아보기(Click) ]

트라이를 어떻게 적용했는지 구체적으로 알아보자. 먼저, 본인은 총 2개의 TRIE를 만들었다.

바로 원본의 문자열을 그대로 저장하기 위한 TRIE 하나와, 문자열을 뒤집은 상태의 문자열을 저장하기 위한 TRIE 하나, 이렇게 총 2개의 TRIE를 선언해서 관리해주었다.

왜냐하면 '검색 키워드'가 "????x" 와 같은 형태로, 앞에 키워드를 모르고, 뒤쪽의 키워드가 주어지는 경우가 존재하기 때문이다.

예를 들어서 "abcde"라는 가사를 TRIE에 저장해놨는데, 검색키워드로 "???de" 가 주어졌다고 생각해보자.

그럼 우리는 이 경우에도 "abcde"를 찾을 수 있어야 한다. 이런 경우를 생각해서 "abcde"가 있으면, "abcde"를 저장하기 위한 TRIE 하나와, "edcba"를 저장하기 위한 TRIE하나를 따로 만들어서 관리해 주었다는 것이다.

그래서 만약 "???de"와 같은 검색 키워드가 주어진다면, 이를 뒤집어서 "ed???"를 뒤집어 놓은 TRIE에서 찾는 방법으로 접근하는 것이다.

지금부터 "abcde"가 있을 때, "abcde"를 그대로 저장하는 것을 "원래 문자열을 저장하는 TRIE" 라고 표현하고, "edcba"를 저장하는 것을 "뒤집은 문자열을 저장하는 TRIE" 라고 표현하겠다.

이렇게 본인은 "원래의 문자열을 저장하기 위한 TRIE"와 "뒤집은 문자열을 저장하기 위한 TRIE" 2개를 만들어서 관리해 주었다.

그리고 본인은 TRIE를 배열로 만들어서 관리해 주었다. 단순히 하나의 Root가 존재하는 TRIE가 아닌, TRIE 배열을 만들어서 관리해 주었다. 배열로 만들어서 관리를 해준 이유는 "문자열의 길이" 때문이다. 문자열을 길이별로 따로 저장하는 것이다.

예를 들어서 "abcde"가 있다면, TRIE Trie[5] 에 저장을 해주었다. 여기서 5번 Index에 저장을 해준 것은, "문자열의 길이가 5입니다" 라는 것을 뜻한다. 검색키워드에서도 문자열의 길이에 따라서 답이 달라질 수 있기 때문에 이렇게 관리를 해주었다.

예를 들어서 "abc???" 가 검색 키워드로 들어온다면, 이는 "길이가 6이면서, 'abc'로 시작하는 가사를 찾고있습니다." 라는 것을 의미한다. 즉 ! 이 "abcde"는 이 경우에는 속하지 않게 된다. 따라서 본인은 2개의 TRIE모두 배열을 만들어서 관리했고, 해당 배열의 Index번호가 의미하는 것은 "문자열의 길이" 이다.

그럼 TRIE를 구현해보자.

본인이 이 문제에서 선언한 TRIE가 가지는 멤버변수는 총 3개가 있다.

{ 그 다음 노드를 가리키기 위한 TRIE형 배열 , 문자열의 끝을 알리는 변수, 노드의 자식 수를 나타내는 변수 }

이렇게 총 3개를 만들어 주었다. 위의 링크가 걸려있는 TRIE에서는 아마, '노드의 자식 수를 나타내는 변수'는 설명에 없었을 것이다. 이 부분은 검색 키워드 때문에 만들어준 변수이다. 문자열을 TRIE에 삽입할 때, 문자 하나 하나 추가할 때 마다 이 변수의 값을 ++ 시켜 주는 것이다. 예를 들어서 TRIE에 "abcde"를 넣는 과정을 생각해보자.

.

가장 처음에는 위와 같이 Root 노드 하나만 존재할 것이다. 위의 Root노드는 Trie[5]의 루트 노드이다. 왜냐하면 "abcde"를 삽입할 것이기 때문에, 길이가 '5'인 TRIE에 넣어주는 것이다.

이 때, 'a'를 넣어보자. 넣을 때, Child의 변수를 ++시켜주어야 한다 !

.

이런식으로 'b','c','d,'e' 도 넣게되면 다음과 같이 될 것이다.

.

여기서 만약 "acdef" 가 들어오면 어떻게 될까 ??

.

위와 같은 형태로 될 것이다. 문자를 하나 추가 할 때 마다, Child 변수의 값을 ++ 시켜주면 위와 같이 값이 설정이 된다.

그런데 이 값을 왜 구한걸까 ??

바로 "탐색 시간을 줄이기 위해서" 사용한 것이다.

위와 같이 TRIE가 구성되어 있을 때, 검색 키워드로 "a????" 가 들어왔다고 생각해보자.

"abcde", "acdef" 2개 모두 위의 검색 키워드로 찾을 수 있는 문자열들이므로 2개를 return 해주어야 한다.

그런데 여기서 굳이, "a????"를 보고, a에서 b로 갔다가, c로 갔다가 d로 갔다가 e로 갔다가 끝나는 표시를 보고 1개 추가 ~

그 이후에 a에서 c로 갔다가, d로 갔다가 e로 갔다가 f로 갔다가 끝나는 표시를 보고 1개 추가~ 해서 총 2개 !

이렇게 탐색을 할 필요가 있을까 ?? 그럴 필요가 없다 ! 왜 ?? 어차피 위의 문자열들은 모두 길이가 '5'인 문자열들이다.

더 많은 문자열들이 위의 TRIE에 존재한다고 하더라도, 모두다 길이가 '5'일 것이다. 왜냐하면 위에서도 말했듯이, 위의 그림은 TRIE 배열의 5번 Index의 TRIE구조이다. 여기서 5번 Index라는 것은 길이가 5인 문자열들만 모아놓은 TRIE라고 말했었다.

즉 ! 어차피 길이가 5인 문자열들이라서, 끝까지 탐색하지 않았을 때, 길이가 맞지 않다는 이유로 Count가 잘못될 일은 없을 것이다. 그리고 우리가 만들어놓은 Child변수의 의미를 생각해보자. 단순히 위에서는 "문자를 하나 추가할 때마다 ++시키세요~" 라고 했는데, 그 의미를 한번 생각해보자. 그 의미를 표현해보면 "현재 문자열로 시작하는 문자열의 갯수" 를 나타내고 있다.

위의 그림에서 'a'의 Child값은 2이다. 즉 ! "이 TRIE 안에는, "a"라는 문자열로 시작하는 문자열의 갯수는 총 2개가 있습니다" 라는 것을 표현하고 있다. 그럼 "ab"를 생각해보자. 검색 키워드로 "ab???"가 주어진 것이다. 그럼 'a'를 지나 'b'까지는 탐색을 해봐야 한다. 그리고 'b'의 Child 수를 보니까 '1'이다. 즉 ! "이 TRIE안에는, "ab"라는 문자열로 시작하는 문자열의 갯수는 총 1개가 있습니다" 라는 것을 표현해 주고 있다. 따라서 ! 우리는 이 변수를 설정해주게 되면 굳이 모든 문자열을 끝까지 탐색을 해볼 필요가 없다.

그래서 위와 같은 멤버변수들을 이용해서 계산해 주었다.

지금까지 TRIE를 정의하고, 어떻게 보면 삽입하는 과정까지 같이 알아보았다.

그럼 찾는 과정을 한번 알아보자.

검색 키워드에서 본인은 총 3가지 경우를 생각해서 구현하였다.

1. "xx???" 형태인 경우

2. "???xx" 형태인 경우

3. 없는 문자열을 검색 키워드로 사용한 경우

먼저 가장 간단하게 3번 경우부터 보자. 먼저 시작부터 없는 문자열일수도 있다.

즉, 우리가 가사로 검색받은 문자열은 "abcde","acdef" 인데, "ab????" 를 찾으라는 경우이다. 앞에서 말한 2개의 가사를 TRIE에 삽입할 때 우리는 5번 Index에 삽입을 했는데, "ab????"는 길이가 6이므로 6번 Index에서 찾을 것이다. 그런데 ! 6번 Index는 한번도 삽입된 적이 없으므로 Root노드 마저 없을 것이다. 즉 ! 이런 경우를 한번 판단해서 '0'을 삽입해 주어야 한다.

두 번째 경우는 중간부터 없는 경우이다. 마찬가지로 "abcde", "acdef"를 입력받았을 때, "abf??" 를 찾으라는 것이다.

우리가 만든 TRIE로 본다면 a -> b로 갔다가 b에서 f 로 가는 노드는 존재하지 않는다. 즉 ! 이렇게 중간에 노드가 존재하지 않는 경우도 그대로 탐색을 종료하고 '0'을 넣어주면 된다.

이제 1번 경우와 2번 경우를 보자. 위에서도 말했듯이, 1번 경우는 "원래의 문자열을 저장하는 TRIE"에서 , 2번 경우는 "뒤집은 문자열을 저장하는 TRIE"에서 탐색을 진행해주면 된다. 탐색의 종료조건은

1. 탐색 중간에 노드가 존재하지 않는 경우 0을 return

2. 1번 경우에 해당하지 않고, '?' 까지 왔다면, 현재 노드의 Child 값을 return 시켜주면 된다.

탐색 부분은 이렇게만 구현해도 되지만, 본인은 한가지 더 추가해주었다.

검색 키워드 제한사항에 보면 "검색 키워드는 중복될 수도 있다." 라는 말이 있다. 즉 ! 똑같은 검색키워드가 10만개가 주어질 수도 있다는 이야기이다. "ab???" 가 10만번 주어졌을 때, 우리는 Child 변수를 이용해서 충분히 끝까지 탐색하지 않아도 되게 만들어 놨지만, "ab???"가 주어졌을 때 답이 '1'이라는 것을 알고난 이후에도 굳이 계속해서 "ab???"를 탐색할 필요가 있을까 ??

어떻게 설정만 잘해준다면 중복된 키워드를 계속해서 탐색할 필요가 없다.

이 부분을 위해서 본인은 STL map을 사용해주었다. map<string, int>로 만들어서, 고유한 키값인 string을 탐색했을 때, 결과값을 int에 저장해 주었다. 즉 ! 처음에는 당연히 이 결과값이 0일 텐데, 한번 탐색한 이후에는 그 결과값을 저장해 주게 될 것이고, 그 이후에는 이 값이 0이 아닐 것이다. 따라서 map을 이용해서 중복된 검색키워드의 탐색 시간을 줄여주었다.

[ 소스코드 ]

#include <string>
#include <vector>
#include <map>
 
using namespace std;
 
struct TRIE
{
    TRIE *Node[26];
    int Child_Cnt;
    bool Finish;
 
    void Insert(const char *Str);
    int Find(const char *Str);
};
 
int Idx = 0;
TRIE *Trie[10010], *R_Trie[10010];
TRIE Nodepool[1000010 * 2];
 
TRIE *Nodeset()
{
    TRIE *NewNode = &Nodepool[Idx++];
    NewNode->Child_Cnt = 0;
    NewNode->Finish = false;
    for (int i = 0; i < 26; i++) NewNode->Node[i] = NULL;
 
    return NewNode;
}
 
void TRIE::Insert(const char *Str)
{
    Child_Cnt++;
    if (*Str == NULL)
    {
        Finish = true;
        return;
    }
 
    int Cur = *Str - 'a';
    if (Node[Cur] == NULL) Node[Cur] = Nodeset();
    Node[Cur]->Insert(Str + 1);
}
 
int TRIE::Find(const char *Str)
{
    if (*Str == '?') return Child_Cnt;
 
    int Cur = *Str - 'a';
    if (Node[Cur] == NULL) return 0;
    return Node[Cur]->Find(Str + 1);
}
 
int Check_State(string S)
{
    if (S[0] == '?') return 0;
    if (S[S.length() - 1] == '?') return 1;
}
 
string Reverse(string S)
{
    string Temp = "";
    for(int i = S.length() - 1 ; i >= 0 ; i--)
    {
        Temp = Temp + S[i];
    }
    return Temp;
}
 
vector<int> solution(vector<string> words, vector<string> queries) 
{
    vector<int> answer;
    for (int i = 0; i < words.size(); i++)
    {
        string S = words[i];
        int Len = S.length();
        if (Trie[Len] == NULL) Trie[Len] = Nodeset();
        Trie[Len]->Insert(S.c_str());
 
        string Reverse_S = Reverse(S);
        if (R_Trie[Len] == NULL) R_Trie[Len] = Nodeset();
        R_Trie[Len]->Insert(Reverse_S.c_str());
    }
 
    map<string, int> MAP;
    for (int i = 0; i < queries.size(); i++)
    {
        string S = queries[i];
        if (MAP.count(S) == 0)
        {
            MAP[S] = i;
 
            int Len = S.length();
            int State = Check_State(S);
 
            if (State == 1)
            {
                if (Trie[Len] == NULL) answer.push_back(0);
                else answer.push_back(Trie[Len]->Find(S.c_str()));
            }
            elsea
            {
                string Reverse_S = Reverse(S);
                if (R_Trie[Len] == NULL) answer.push_back(0);
                else answer.push_back(R_Trie[Len]->Find(Reverse_S.c_str()));
            }
        }
        else answer.push_back(answer[MAP[S]]);
    }
    return answer;
}