[2018 KAKAO BLIND RECRUITMENT] [3차] 자동완성

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

코딩테스트 연습 - [3차] 자동완성 | 프로그래머스

 

 

 

이 문제는 Trie 자료 구조를 사용해서 풀어야 한다.

Trie 자료 구조가 익숙치 않으신 분들은, 다음 글을 참고하시길 바란다.

 

 

 

---

https://real-012.tistory.com/41?category=769031

Trie(트라이) 자료구조 정의, 예제 코드

 

 

 

문제를 이해하다 보면, Trie 자료구조가 필요하다고 느낄 것이다. 다른 방법으로도 풀 수 있겠지만, 이 문제는 Trie 자료구조가 가장 적당하고 빠를 것이다. 다른 방식의 풀이는 최소한 N * N의 시간복잡도가 필요할 것으로 예상된다.

 

 

 

 

Trie 자료구조를 이용하면 문제는 간단해진다. 이 문제를 풀기 위해서는, cnt, Trie* 2가지 변수가 있으면 충분하다. 

 

 

 

cnt = 해당 문자의 출현 횟수 및 종료 역할

Trie* = Trie형의 다음 문자 주소값(a - z)

 

 

 

 

insert 함수가 동작하면서, Trie 자료구조가 완성될 것이다. 두 문자열이 있을 때, 중복되는 문자들은 모두 들어가야 하므로 정답에 더해져야한다. 따라서, cnt > 1인 경우를 찾아야 한다. 또한, 처음 cnt == 1인 순간에도 신경을 써야한다.

 

 

 

 

gone의 경우에는 'n'은 cnt가 1이지만, 구분하기 위해서 gon까지 입력을 하므로, 처음으로 cnt가 1이 되는 순간까지만 정답의 문자 개수에 포함시켜주면 된다.

 

 

 

---

 

 

 

해설코드(C++).

 

 

 

#include <string>

#include <vector>

#include <iostream>

#include <algorithm>

#include <cstring>

 

using namespace std;

 

int result = 0;

 

struct Trie {

    bool finish = false;

    int cnt = 0;

    Trie* next[26];

    Trie() : finish(false) {

        memset(next, 0, sizeof(next));

    }

 

    void insert(const char* key) {

        if ((*key) == '\0') {

            if (cnt == 1) {

                finish = true;

            }

            return;

        }

 

        int curr = (*key) - 'a';

        if (!next[curr]) {

            next[curr] = new Trie();

        }

        next[curr]->cnt += 1;

        next[curr]->finish = false;

        next[curr]->insert(key + 1);

    }

 

    void count() {

        if (cnt > 1)

            result += cnt;

        else if (cnt == 1) {

            result += 1;

            return;

        }

 

        if (finish) {

            return;

        }

 

        for (int i = 0; i < 26; i++)

        {

            if (next[i])

                next[i]->count();

        }

    }

};

 

int solution(vector<string> words) {

    Trie* trie = new Trie();

    for (int i = 0; i < words.size(); i++) {

        trie->insert(words[i].c_str());

    }

    trie->count();

 

 

    return result;

}

 

int main(void) {

    solution({ "go","gone","guild" });

}