[ 프로그래머스 [3차]자동완성 (Lv4) ] (C++)

프로그래머스의 [3차]자동완성(Lv4) 문제이다.

[ 문제풀이 ]

문자열이 주어지고 주어진 모든 문자열을 입력하는데 눌러야 하는 버튼의 횟수를 구해야 하는 문제이다.

본인은 문자열을 관리하기 위해서 'TRIE(트라이)' 자료구조를 구현해서 접근해 보았다.

본격적인 풀이과정을 알아보기 전에, 트라이에 대해서 모른다면 아래의 글을 읽고 오도록 하자.

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

위의 글을 베이스로 해서 이 문제에 알맞게 트라이를 구현해보자.

먼저 본인은 'TRIE'라는 구조체를 선언해서 사용해주었는데, 그 안에서 사용되는 멤버변수로는

{ 그 다음을 가르키는 노드배열(26칸 : 알파벳) , 자식 문자열의 갯수 , 문자열의 끝을 나타내는 변수 } 이렇게 3개를 사용해 주었다.

먼저, '다음을 가르키는 TRIE형 노드배열(26칸)'은 설명되어있는 트라이와 동일한 역할을 한다.

문자열에서 문자 하나 하나를 노드를 생성해주면서 관리하기 위해서 선언해준 변수이다.

'문자열의 끝을 나타내는 변수' 또한 마찬가지이다. 말 그대로, 트라이에서 문자열의 끝을 나타내주는 변수이다.

이번 문제에서의 핵심은 '자식 문자열의 갯수'를 나타내는 변수이다.

바로 이 변수를 통해서 우리는 몇 개의 문자를 입력해야 되는지 판단할 것이다.

예를 들어서 { ab , abc , ade , def } 를 입력하는 상황을 가정해보자.

우리는 "ab"를 누르기 위해서는 2번을, "abc"를 누르기 위해서는 3번을, "ade"를 누르기 위해서는 2번을, "def"를 누르기 위해서는 1번을 누르면 된다. 그럼 위의 4개의 문자열을 트라이로 만들어 보자. 다음과 같이 존재하게 될 것이다.

.

가장 위에 'R'은 Root를 나타낸다. 그리고 ab, abc, ade, def 가 위와 같은 형태로 구현될 것이다. 빨간색 점은 각 문자열이 끝나는 지점을 표시해 놓은 것이다.

그럼 여기서 우리가 만들어 놓은 '자식 문자열의 갯수'를 나타내는 변수는 어떻게 적용되는지 알아보자.

이 변수는 문자열이 끝날 때 까지 계속해서 ++ 되는 식으로 구현이 되는데, 이렇게 구현하게 되면 어떻게 되는지 알아보자.

지금부터 이 변수를 'Child' 변수라고 부르겠다.

위의 그림 말고, 가장 초기에 TRIE에 루트 노드만 존재한다고 생각하고, 아무런 문자열도 들어오지 않은 상태에서 다시 "ab"부터 트라이에 삽입해보자.

.

가장 먼저, "ab"에서 'a'가 트라이에 삽입되면서 루트노드에 Child변수가 ++ 되어서, 1이 되었다. 그리고 현재 노드는 'a'가 된다.

그리고 이어서 'b'를 삽입해보자.

.

위와 같이 될 것이다. 현재 노드는 'b'이기 때문에 그 다음 문자로 가보자.

.

위와 같이 b다음의 문자는 없기 때문에, 빨간점으로 표시가 될 것이다. 물론 이 경우에도 'b'노드에 대한 Child변수가 ++ 되어진다. 따라서 위와 같은 형태로 생성되어진다.

그 다음 "abc"를 한번 삽입해보자. 지금부터는 과정을 그림 하나 하나 말고 말로 이해해보자.

루트 노드에서 'a'로 갈 때, 루트노드의 Child변수가 ++ 되어질 것이다.

'a'노드에서 'b'로 갈 때, 'a'노드의 Child변수가 ++ 되어질 것이다.

'b'노드에서 'c'로 갈 때, 'b'노드의 Child변수가 ++ 되어질 것이다.

'c'노드에서 Null로 갈 때, 'c'노드의 Child변수가 ++ 되어질 것이다.

즉 ! 위의 결과를 그림으로 나타낸다면 다음과 같아진다.

.

이렇게 구현되어 질 것이다.

그 다음, "ade"를 삽입해보자.

루트노드 → 'a'로 갈 때, 루트노드의 Child변수 ++

'a' → 'd'로 갈 때, 'a'노드의 Child변수++

'd' → 'e'로 갈 때, 'd'노드의 Child변수 ++

'e' → Null로 갈 때, 'e'노드의 Child변수++

즉 ! 다음과 같아질 것이다.

.

마지막으로 "def"를 삽입해보면, 다음과 같아질 것이다.

.

 그럼 이제부터 위의 변수가 무엇을 의미하는지 한번 생각해보자.

계산하라는 대로 계산을 하면서 트라이를 구현하긴 했는데, 위의 변수들로 어떻게 정답을 찾아낼 수 있는지 알아보자.

각 숫자들이 의미하는 것을 잘 보면 "현재 노드를 기준으로, 자기 아래에 몇 개의 문자열들이 더 존재하는지" 를 가르쳐 준다.

루트 노드를 보게 되면 '4'라는 값을 가지고 있다. 실제로 루트노드 아래에는 "ab","abc","ade","def" 라는 4개의 문자열이 존재하고 있다.

그럼 '3'의 값을 가지고 있는 'a'노드를 한번 보자. 'a'노드 아래에는 실제로 "ab", "abc", "ade" 라는 3개의 문자열이 존재한다.

그럼 이 갯수로 몇 번을 누르는지 어떻게 판단해야 할까 ?? 문제에서 이야기하는 기능은 '자동완성' 기능이다.

즉 ! "특정 버튼을 눌렀을 때, 그 버튼 이후에 존재하는 '유일한 문자열'이 있다면 자동완성이 된다." 라는 것이다.

여기서 '유일한 문자열' 이라는 것을 어떻게 판단할까 ?? 바로 우리가 위에서 만들어 놓은 'Child'변수의 값이 '1'이라는 것으로

판단할 수가 있다. 왜 ?? 'Child변수'가 의미하는 것은 위에서도 말했듯이 "현재 노드를 기준으로, 자기 아래에 몇 개의 문자열들이 더 존재하는지"를 나타낸다고 했다. 그런데 ! 자기 아래에 '1개의 문자열만이 더 존재한다' 라는 것은 해당 노드 까지 왔을 때, 그 이후에 존재할 수 있는 문자열은 유일한 문자열이라는 것을 의미하기 때문이다.

따라서 우리는 버튼을 누르는 횟수를 다음과 같이 정의할 수 있다.

1. 현재 노드가 가지고 있는 Child변수의 값이 1이면 ? == 지금까지 누른 횟수를 return.

2. 현재 노드가 문자열의 마지막을 나타내고 있는 변수라면 ? == 지금까지 누른 횟수를 return.

이렇게 판단할 수가 있다.

2번 같은 경우를 보자. "ab"를 실제로, 'a'와 'b' 2개를 모두 다 눌러주어야 한다. 그리고 'a'와 'b'는 모두 Child변수의 값이 1이 아니다. 따라서, Child변수의 값이 1이라는 것만으로 판단이 되지 않는 경우가 존재한다.

하지만 'ab'를 누를 때는 2번만 누르면 된다. 즉 ! Child변수의 값이 1이 되지 않더라도, 현재 노드가 문자열의 마지막을 나타내는 문자라면 그대로 누른 횟수를 return 해주면 된다.

그럼, 위의 상황에서 "def" 문자열을 생각해보자. 루트노드에서 'd'노드 까지 오게 될 것이다. 그런데 ? 'd'노드가 가지고 잇는 Child변수의 값은 '1'이다. 즉 ! 'd'이후에 존재하는 문자열은 '유일하게 딱 1개의 문자열'만이 존재한다는 것이고, 이런 경우에는 자동완성이 되기 때문에, 'def'는 '1'번만 눌러도 자동완성으로 완성시킬 수 있음을 의미한다.

[ 소스코드 ]

#include <string>
#include <vector>
 
using namespace std;
 
struct TRIE
{
    TRIE *Node[26];
    int Child;
    bool Finish;
 
    void Insert(const char *Str);
    int Find(const char *Str, int Cnt);
};
 
int Trie_Idx;
TRIE Nodepool[1000010];
 
TRIE *Nodeset()
{
    TRIE *NewNode = &Nodepool[Trie_Idx++];
    for (int i = 0; i < 26; i++) NewNode->Node[i] = NULL;
    NewNode->Child = 0;
 
    return NewNode;
}
 
void TRIE::Insert(const char *Str)
{
    Child++;
    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, int Cnt)
{
    if (Child == 1 || *Str == NULL) return Cnt;
 
    int Cur = *Str - 'a';
    return Node[Cur]->Find(Str + 1, Cnt + 1);
}
 
int solution(vector<string> words) 
{
    Trie_Idx = 0;
    int answer = 0;
    int N = words.size();
    TRIE *Root = Nodeset();
    for (int i = 0; i < N; i++) Root->Insert(words[i].c_str());
    for (int i = 0; i < N; i++) answer = answer + Root->Find(words[i].c_str(), 0);
    
    return answer;
}