[BOJ/C++] 문자열 집합

1. 개요

https://www.acmicpc.net/problem/14425

14425번: 문자열 집합

1-1. 설명

총 N개의 문자열로 이루어진 집합 S가 주어진다.

입력으로 주어지는 M개 문자열 중 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성한다. 

1-2. 제한 사항

 - 첫째 줄에 문자열 개수 N과 M이 주어지며, 각각 1 이상 10,000이하 자연수

 - 다음 줄 N개에는 집합 S에 포함되어 있는 문자열

 - 다음 M개 줄에는 검사해야 하는 문자열

 - 입력으로 주어지는 문자열은 모두 알파벳 소문자로 이루어져 있으며 길이는 500을 넘지 않음

---

2.구현

2-1. 풀이

간단하게 set으로도 풀 수 있으나, Trie 자료구조를 연습하기 위해 Trie 자료구조를 구현하여 풀어냈다. 주의 사항은 string 인자를 넘길때  reference 형태(&)로 넘겨야 시간초과가 나지 않는다. reference 형태로 넘기지 않고 변수 그대로 인자에 전달할 시 복제가 되어 시간을 더 소요하기 때문이다. 

• Trie 구조

struct Trie {
    bool finish; // 끝나는 지점 확인
    Trie* node[SIZE]; // 알파벳 개수가 26개이므로, 26개에 대한 Trie

    Trie() { // 할당 및 생성
        finish = false;
        fill(node, node + SIZE, nullptr);
    }
    ...
}

Trie구조는 위와같이 끝점을 알 수 있는 finish와 각 알파벳의 node가 저장될 Trie pointer이다. 쉽게 생각해 현재 Trie 노드의 자식 노드로 생각하면 될 것 같다. 생성될 때 finish와 node를 할당해준다. 

• Trie Insert

    void insert(string &str, int index) {  // string 문자를 삽입하기 위한 과정
        if (str.size() <= index) {
            finish = true;
            return;
        }
        int current = str[index] - 'a'; // 현재 문자를 가져옴
        if (node[current] == nullptr) node[current] = new Trie();
        // 연결된 노드가 존재하지 않을 때 노드 생성 후 그다음 문자열 탐색
        // -> 기존 다른 문자열에 의해 노드 존재시 PASS
        node[current]->insert(str, index + 1);
        // 다음 문자열로 넘어가는 과정
    }

string 문자를 저장하기 위한 insert 함수이다.

index 크기가 string의 사이즈보다 크거나 같으면 끝점에 도달한 것으로 생각해 finish를 true로 변경하고 종료한다. 그 외에는 현재 문자를 가져오기 위해 current에 문자열 알파벳 인덱스를 저장한다. 해당 알파벳이 가리키는 노드가 없다면 새롭게 노드를 생성하고 다음 문자열을 탐색(insert)해준다. 

• Trie Find

    bool find(string &str, int index) { // 문자열 마지막까지 탐색했을 경우
        if (str.size() <= index) return finish;

        int current = str[index] - 'a';
        if (node[current] == nullptr) return false; // 노드 생성되지 않았을 때
        return node[current]->find(str, index + 1);
    }

마지막으로 해당 문자열이 존재하는지 알아내기 위해 만들어진 find 함수이다. 문자열이 마지막까지 탐색되었고 finish가 true이면 find는 존재하는 것으로 인지하고 true를 반환한다. 검색하던 도중 노드가 생성되지 않았거나 마지막까지 도달했는데 finish가 false이면 false를 반환한다. 

2-2. 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

#define SIZE 26

using namespace std;

struct Trie {
    bool finish;
    Trie* node[SIZE];

    Trie() {
        finish = false;
        fill(node, node + SIZE, nullptr);
    }

    void insert(string &str, int index) {
        if (str.size() <= index) {
            finish = true;
            return;
        }
        int current = str[index] - 'a'; 
        if (node[current] == nullptr) node[current] = new Trie();
        node[current]->insert(str, index + 1);
    }
    bool find(string &str, int index) {
        if (str.size() <= index) return finish;

        int current = str[index] - 'a';
        if (node[current] == nullptr) return false;
        return node[current]->find(str, index + 1);
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, M;
    cin >> N >> M;

    Trie* root = new Trie();
    string str;

    for (int i = 0; i < N; i++) {
        cin >> str;
        root->insert(str, 0);
    }

    int result = 0;
    while (M--) {
        cin >> str;
        if (root->find(str, 0)) result += 1;
    }
    cout << result << "\n";
    return 0;
}

 

---

참고 문서

https://yabmoons.tistory.com/379

[ 자료구조 트라이(TRIE) ] 개념과 구현방법 (C++)

https://eun-jeong.tistory.com/29

[자료구조] 트라이 (Trie) C++ 구현