[프로그래머스] : [3차] 자동완성

#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <set>
#include <memory.h>

using namespace std;

typedef struct s_dochoi{
    int cnt;
    s_dochoi *next[26]; //a~z까지의 다음 구조체 포인터 배열
}t_dochoi;

s_dochoi *first[26]; // 처음 구조체 

int solution(vector<string> words) {
    int answer = 0;
    memset(first, 0, sizeof(t_dochoi)); // 구조체 초기화
    
    for(int i = 0; i < words.size(); i++)
    {
        t_dochoi* base;
        if (first[words[i][0] - 'a'] == 0)// 값이 아직 없으면
        {
            t_dochoi* dochoi = new t_dochoi; //새로 동적할당
            memset(dochoi, 0, sizeof(t_dochoi)); // 초기화
            dochoi->cnt = 1; // 개수 1로 초기화
            first[words[i][0]-'a'] = dochoi; //값 대입
              
        }
        else
            first[words[i][0]-'a']->cnt += 1; // 값이 있으면 카운트만 세준다.
        base = first[words[i][0] -'a']; // next 구조체(링크드리스트 같이 생각)
        for(int j = 1; j <words[i].size(); j++)
        {
               if (base->next[words[i][j] - 'a'] == 0) // 할당이 안되어있으면
            {
                t_dochoi* dochoi = new t_dochoi; // 동적할당
                memset(dochoi, 0, sizeof(t_dochoi)); //초기화
                dochoi->cnt = 1;// 카운트 초기화
                base->next[words[i][j] - 'a'] = dochoi; // 대입
            }
            else
                base->next[words[i][j] - 'a']->cnt += 1; // 할당이 되어있으면 카운트 +1
             base =  base->next[words[i][j] - 'a']; // 다음 포인터 주소로 넘어간다.
        }
    }
    
    for(int i = 0; i < words.size(); i++)
    {
        t_dochoi* base;
        base = first[words[i][0] -'a'];

        int word_size = words[i].size();
        
         if (base->cnt == 1  || word_size == 1) // 자기 혼자만 존재하거나 크기가 1이면 끝
         {
            answer += 1;
            continue;
        }
        for(int j = 1; j < word_size; j++)
        {
            if (base->next[words[i][j] - 'a']->cnt == 1 || j == word_size - 1) // 자기 혼자만 존재하거나 크기가 최대이면 끝
            {
                answer += (j + 1);
                break;
            }
             base =  base->next[words[i][j] - 'a'];
        }
    }
    return answer;
}