프로그래머스 Level 4 자동완성

자동완성 (프로그래머스 Level 4)

https://school.programmers.co.kr/learn/courses/30/lessons/17685

솔직히 어려웠다
단어 검색에 ‘트라이’ 자료구조를 적용할 수 있기에
해당 자료구조를 구현하여 푸는 쪽으로 문제를 풀었다

다만, vs 에서는 유니크 포인터가 아니라 일반적인 node를 그대로 사용하였으나
프로그래머스에서는 해당 방식이 error가 발생하였기에 ‘유니크 포인터’로 바꾸어주었다
(node의 map 부분에서 ‘재귀적’으로 정의 되기에, 컴파일러가 node의 크기를 알 수 없었다고 한다)
(vs에선 컴파일러 구현 방식의 차이로 정상 컴파일이 되었을 수 있다고…)

문제로 돌아가자면,
트라이의 개념을 구현하여 간단하게 풀어보려 하였다

1. string의 각 char를 ‘node’로 표현하여
   연결되어 있는 단어를 표현한다
   g -> o -> n -> e
   g -> u -> i -> l -> d
   이런식으로 g 하나의 단어에서 o와 u의 node를 별도로 가지고 있게 된다
   
2. count를 이용하여, 해당 단어가 얼마나 사용되었는지를 표시
   go 와 gone은 둘다 ‘go’ 부분을 공유하나, go는 ‘끝나는’ 부분이 없기에
   단어 자체의 ‘개수’를 넘어서는지에 대한 체크가 필요
   
3. insert와 findCount를 하위 node에서도 같은 방식으로 작동하도록
   재귀적으로 구현
   

Code

#include <string>
#include <vector>
#include <unordered_map>
#include <memory>
#include <algorithm>

using namespace std;

int solution(vector<string> words) {
    struct node
    {
        unordered_map<char, unique_ptr<node>> m;
        int count = 0;

        void insert(const string& str, int ind)
        {
			// 단어 다 쳤으니 종료
            if (ind >= str.size())
                return;

            if (m.find(str[ind]) == m.end())
            {
                m[str[ind]] = make_unique<node>();
            }

			// 하위 노드에서 다음 단어로
            m[str[ind]]->count += 1;
            m[str[ind]]->insert(str, ind + 1);
        }

        int findCount(const string& str, int ind)
        {
			// 단어 이미 다 쳤으니 종료
			// 사실상의 최솟값 보장
            if (ind >= str.size())
                return ind;

			// 다음 목표에 '하나' 밖에 없다면 더 검색할 필요 없음
            if (m[str[ind]]->count == 1)
                return ind + 1;

			// 하위 노드에서 다음 단어로
            return m[str[ind]]->findCount(str, ind + 1);
        }
    };

    int answer = 0;
    node start;
    for (const auto& word : words)
    {
        start.insert(word, 0);
    }

    for (const auto& word : words)
    {
        answer += start.findCount(word, 0);
    }

    return answer;
}