문제 푼 날짜 : 2021-07-19

문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17685

접근 및 풀이

TRIE 자료구조를 구현할 수 있어야 풀 수 있는 문제였다.
TRIE에 대한 개념은 설명은 이 곳를 참고하였다.
TRIE를 구현한 코드는 다르지만 큰 틀에서 봤을 땐 대동소이하다.

아래의 알고리즘을 따라 구현해주었다.

1. 주어진 words에 대해서 TRIE를 생성한다. (count 변수는 현재 노드에서 연결된 자식 문자열의 개수이다.)
2. 주어진 words에 따라서 search를 진행해준다. (문자열의 문자를 탐색할 때마다 횟수를 세어준다.)
3. 진행하다가 현재 노드의 count 값이 1이거나, 마지막 노드라면 몇 번 진행했는지 횟수를 return 해준다.

이 때, 3. 에서 count가 1일 때 return해주는 이유는 그 아래로는 다른 문자열이 존재하지 않고 유일하다는 소리이므로 그 이후의 문자에 대해서는 탐색을 진행할 필요가 없기 때문이다.

코드

#include <string>
#include <vector>

using namespace std;

class Trie {
private : 
    Trie *child[26];
    int count;
    
public :
    Trie() : child(), count(0) {}
    void Insert(string str) {
        Trie *curr = this;
        for (char c : str) {
            curr->count++;
            if (curr->child[c - 'a'] == nullptr) {
                curr->child[c - 'a'] = new Trie();
            }
            curr = curr->child[c - 'a'];
        }
        curr->count++;
    }
    int Search(string str) {
        Trie *curr = this;
        int ret = 0;
        for (char c : str) {
            ret++;
            curr = curr->child[c - 'a'];
            if (curr->count == 1) {
                return ret;
            }
            if (curr == nullptr) {
                return ret;
            }
        }
    }
};

int solution(vector<string> words) {
    int answer = 0;
    Trie *t = new Trie();
    
    for (string str : words) {
        t->Insert(str);
    }
    for (string str : words) {
        answer += t->Search(str);
    }
    return answer;
}

결과

피드백

TRIE 자료구조 잊지말고 익혀두자