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

문제

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

아이디어1

Trie 구조를 사용

클래스

class trie {
public:
    trie()
    {
    }
    
    ~trie()
    {
        for (auto& c : child)
        {
            delete c.second;
        }
        child.clear();
    }
    
private:
    unordered_map<char, trie*> child;
    int count = 0;
};

• 공통된 글자는 부모 노드가 됨
• unordered_map (해쉬)을 이용해서 자식들의 key와 노드로 보관
  • 해쉬를 이용하면 원하는 다음 글자의 자식을 O(1)으로 빠르게 찾을 수 있음

아이디어2

주어진 단어들을 통해 노드를 생성

추가 함수

void insert(string word)
    {
        trie* cur = this;
        
        for (int i = 0; i < word.size(); ++i)
        {
            char key = word.at(i);
            
            auto iter = cur->child.find(key);
            if (iter != cur->child.end())
            {
                cur = iter->second;
            }
            else
            {
                trie* temp = new trie;
                cur->child.emplace(key, temp);
                cur = temp;
            }
            cur->count++;
        }
    }

• root 노드로부터 호출
• find 함수를 통해서 iterator를 찾고 없으면 추가
  • operator[]를 통해서 하는 경우도 있는데 find 함수를 사용하는 것이 효율적이고 코드면에서도 맞음
    1. 없으면 element를 생성하기 때문에 단일 책임 원칙에 맞지 않음 -> 검색과 생성을 분리
    2. operator[]는 호출할 때마다 검색을 해서 효율 안 좋음 -> find를 통해 한 번만 검색, emplace나 push를 통해 한 번만 생성
• 공통된 글자만큼 입력을 해야 구분을 할 수 있기 때문에 해당 글자를 지나갈 때 마다 카운트 +1

아이디어3

Trie 구조에서 DFS를 통해 카운트가 1이 나올 때까지 카운트를 더하면 총 입력해야하는 횟수

합 구하기

    void sol(int& answer)
    {
        answer += count;
        
        if (count == 1)
        {
            return;
        }
            
        for (auto c : child)
        {
            c.second->sol(answer);
        }
    }

• 1이 나오면 그 뒤로는 자동완성 가능
• 그 외를 다 더하면 자동완성을 위해 총 입력해야하는 횟수를 구할 수 있음

실행

int solution(vector<string> words) {
    int answer = 0;
    
    trie root;
    
    for (string word : words)
    {
        root.insert(word);
    }
    
    root.sol(answer);
        
    return answer;
}

마무리

• 처음에 생성할 때 word를 넘겨주면서 key를 만들고 나머지를 넘겨주면서 생성하니 string을 계속 복사해서 테스트 케이스22에서 시간 초과가 나옴
  • word를 한 번만 받아와서 쭉 생성하는 방식으로 바꿈
• 다른 사람의 코드가 더 느릴 수 밖에 없었는데 내 코드가 더 시간이 걸리길래 확인해보니 할당 해제에 대한 시간이 추가 됨
  • 그래도 delete는 해주자