[C++로 풀이] 자동 완성 (트라이 자료구조) ⭐⭐⭐⭐

📌 자동 완성

난이도 ⭐⭐⭐⭐

🚀 문제

🚀 내 풀이 ⭕

트라이에 관한 더 자세한 설명은 이 포스트를 참고해주세요. 👉 (C++) 문자열 집합 : 트라이 자료구조

이 문제는 트라이 자료구조 문제로, 아래 두 문제와 유사하다. 두 문제를 짬뽕해서 푸는 느낌!!

• [백준 5670][💚4] 휴대폰 자판 (트라이, 원하는만큼 입력 받기)
  • 이 문제도 접두사를 가지고 자동완성 가능 여부를 판별하는 문제인데, 이 백준 5670 번 문제는 현재 이 문제와 자동완성 가능 여부 판별 기준이 다르다.
    • 백준 “휴대폰 자판” 👉 다음 글자 후보가 유일해야 다음 글자는 자동완성이 가능
      • 자식이 딱 한개인지만 가리면 됐다. 중복 되는게 없거나 접두사가 싹 다 공통적이거나 둘 중 하나여야 가능하기 때문이다.
      • word, world 가 있다면 wo 까지만 입력 되어도 다음 글자 후보는 r 뿐이므로 r은 자동입력이 됨.
    • 카카오 “자동완성” 👉 뒤의 문자열 후보가 유일해야 뒤의 문자열은 자동완성이 가능
      • 자식이 한개이되 공통된 접두사이면 안됨. 유일한 문자열이어야 함. 자식이 한개라는 것은 그게 유일해서일 수도 있고 싹 다 공통적인 접두사라 그럴 수도 있어서 이 자식 한 개라는 정보만으로 판별할 수는 없음. 그러므로 노드마다 접두사 횟수 카운팅 미리 해놓아야 한다.
      • word, world 가 있다면 wo 까지 입력 해도 그 뒤의 문자열이 word가 될지, world가 될지 모르기 때문에 자동 입력 되지 않음.
• [C++로 풀이] 가사 검색 (트라이 자료구조, 문자열 검색, 이분 탐색) ⭐⭐⭐⭐
  • 이 문제는 오직 중복 되는게 없고 유일한 접두사여야지만 자동완성이 가능하기 때문에 카카오 가사 검색 문제처럼 노드마다 중복되는 횟수를 저장하고 있어야 한다. 즉, 첫 문자부터 이 문자까지를 접두사로 가지는 문자열의 개수를 미리 세 놓아야 한다.
    • 트라이의 특성 상, 가사 검색 문제처럼 트라이에 문자열들 추가할 떄 노드마다 1 씩 더해주기만 하면 자연스럽게 구할 수 있게 된다.

---

• 1️⃣ 삽입 👉 모든 노드에 count 변수를 두어, 이 노드를 지날 떄마다 1 증가시킨다. 즉, 중복 접두사 횟수를 구해놓도록!
• 2️⃣ 탐색 👉 해당 글자(=노드)까지를 접두사로 가지는 문자열의 개수가 1 개일 떄만 자동완성 가능. 2 개 이상이라면 수동 입력 해야 하므로 입력 횟수를 카운팅하면 된다.

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

class Trie {
private:
    int count = 0;
    unordered_map<char, Trie*> child;
public:
    void Insert(string str) {
        Trie* now = this;
        for (int i = 0; i < str.length(); ++i) {
            if (now->child[str[i]] == nullptr)
                now->child[str[i]] = new Trie;
            now = now->child[str[i]];
            now->count++;
        }
    }

    int AutoComplete(string str) {
        int numOfInput = 1; // 모든 첫 문자들은 무조건 입력해야하니.. 1 에서 시작
        Trie* now = child[str[0]]; // 루트 말고 첫 문자에서 시작하기
        for (int i = 1; i < str.length(); ++i) {
            if (now->count > 1)
                numOfInput++;
            now = now->child[str[i]];
        }
        return numOfInput;
    }
};

int solution(vector<string> words) {
    int answer = 0;
    Trie root;

    for (string word : words)
        root.Insert(word);

    for (string word : words)
        answer += root.AutoComplete(word);

    return answer;
}

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기