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

 

 

문제

문제 설명

 

[문제 요약]

​

자동완성 기능을 넣기 위해서 한번이라도 입력된 단어는 자동으로 출력되도록 기능을 구현하기로 했다.

 

이 때, 앞부분이 같은 단어라면 구분을 위해서 구분이 될 때 까지 단어를 입력해야한다.

 

만약 goat와 gone이 있다면 구분을 위해 goa와 gon을 입력해 주어야 한다. 그래서 입력해야 할 문자의 수는 6이다.

​

 

 

풀이

 

[풀이]

 

처음에 보고 trie 알고리즘을 활용하면 쉽게 풀 수 있을 것 같아서 trie 알고리즘을 활용해 풀었다.

 

그런데 풀고나서 다른 사람들의 풀이를 보니 정렬을 활용해 푼 사람들이 많았다.

게다가 테스트 케이스에서는 더 빨랐다... ㅠㅠ

 

정렬을 활용한 풀이는 앞이나 뒤에 오는 단어와 비교해서 몇 글자를 추가해야하는지를 비교해 추가하는 방법이였다. 이 방법은 정렬만 하면 비교하는 코드는 쉽게 구할 수 있는 방법이다.

​

나는 trie를 활용해 풀었는데, trie구조를 활용해 단어를 전부 추가하고 단어를 추가할 때마다, 노드에 +1씩 수를 증가시켜서 저장하도록 구현했다.

 

이후 단어를 추가하는 과정이 끝나면, 단어를 찾는 함수를 구현하고 노드에 저장된 수가 1이 나오면 그 때의 깊이, 즉 입력해야하는 단어의 길이를 return하도록 했다.

​

아래 그림을 보면 이해가 더 쉽다.

goat, gone, guild의 단어가 있다면 다음과 같이 노드에 수를 저장할 수 있다.

다른 단어와 구분이 되기 위해서는 같은 트리에서 특정 노드에 한번만 방문을 하면 된다는 뜻과 같다.

그래서 goat와 gone를 구분할 수 있는 최소 깊이인 3을 각각 return하고, guild는 처음으로 1이 나오는 깊이 2를 return하면 된다.

이렇게 각각 단어마다 return한 값을 더하면 정답인 8이 나오게 된다.

​

[아이디어 정리]

1. trie 알고리즘을 이용해 단어들을 트리에 넣는다.
2. 단어들을 넣을 때 마다 방문한 노드에 +1씩 count를 더한다.
3. 이후 트리에서 단어를 찾을 때, 1이 나오면 그 때의 단어의 깊이를 return한다. (만약 최대 길이라면 최대 길이를 return한다)

 

 

Code

 

 

#include <string>
#include <vector>
#include <iostream>
using namespace std;
struct trie
{
    int cnt = 0;
    trie* next[26];

    trie() {
        for (int i = 0; i < 26; ++i) {
            next[i] = NULL; // next 배열 초기화
        }
    }

    void insert(const char* word) {
        if (*word == '\0') {
            return;
        }

        int index = *word - 'a';
        if (next[index] == NULL) {
            next[index] = new trie(); // 새 노드 동적 할당
        }
        next[index]->insert(word+ 1); // 다음 문자 삽입
        next[index]->cnt+=1;
    }

    int find(const char* word, int idx)
    {
        int index = *word - 'a';
        if (*word=='\0')
        {
            return idx;
        }
        if (next[index]->cnt==1)
        {
            return idx+1;
        }
        return next[index]->find(word+1, idx+1);        
    }

};


int solution(vector<string> words) {
    int answer = 0;
    trie T;
    for (int i = 0; i < words.size(); i++) {
        T.insert(words[i].c_str()); // 문자열 포인터 전달
    }
    for (int i=0; i<words.size(); i++)
    {
        answer+=T.find(words[i].c_str(),0);
    }
    return answer;
}

 

---

 

trie 자료구조를 처음 구현해 봤는데, 생각보다 고생했다.

처음에 생성자를 만들지 않아서 초기화를 안 시켜준 것과 화살표 연산자의 사용에 안 익숙한게 가장 큰 이유였다...

 

나중에 아무것도 안보고 trie 함수를 한번 구현하는 연습이 필요할 것 같다...

 

프로그래머스