Computer >> 컴퓨터 >  >> 프로그래밍 >> 프로그래밍

C++ 데이터 구조 설계: 단어 추가 및 와일드카드 검색 구현하기

문제 개요

이번 글에서는 다음 두 가지 연산을 지원하는 데이터 구조를 설계해 보겠습니다.

  • addWord(word) – 새로운 단어를 저장합니다.

  • search(word) – 저장된 단어를 검색합니다.

여기서 search(word) 메서드는 일반 문자열뿐만 아니라 알파벳 소문자(a~z)와 마침표(.)로만 구성된 정규식 형태의 문자열도 처리할 수 있어야 합니다. 마침표(.)는 임의의 한 글자를 대체할 수 있는 와일드카드 역할을 합니다.

예를 들어 "bad", "dad", "mad" 세 단어를 미리 추가해 둔 상태에서 검색을 수행하면 결과는 다음과 같습니다.

  • search("pad") → false

  • search("bad") → true

  • search(".ad") → true

  • search("b..") → true

풀이 접근 방법

이 문제는 트라이(Trie) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 전체 풀이 과정은 아래와 같습니다.

  1. insertNode() 메서드를 먼저 정의합니다. 이 메서드는 루트 노드 참조(head)와 문자열 s를 받아 단어를 트라이에 삽입하며, 동작 방식은 다음과 같습니다.

    • curr := head, n := 문자열 s의 길이로 초기화합니다.

    • i를 0부터 n–1까지 반복하면서:

      • x := s[i]

      • curr의 자식 중 x에 해당하는 노드가 존재하지 않으면 새 노드를 생성합니다.

      • curr := curr의 x번째 자식 노드로 이동합니다.

    • 반복이 끝난 후 마지막 노드의 isEnd 값을 true로 설정하여 단어의 끝임을 표시합니다.

  2. addWord() 메서드에서는 위에서 정의한 insertNode()를 호출합니다.

  3. check() 메서드를 정의합니다. 현재 노드 curr, 문자열 s, 인덱스(초기값 0)를 매개변수로 받아 재귀적으로 동작합니다.

    • 인덱스가 문자열 길이와 같다면 curr의 isEnd 값을 반환합니다.

    • s[index]가 마침표(.)라면, 알파벳 26글자(‘a’~‘z’) 각각에 대해 해당 자식 노드가 존재하고 check(child[x], s, index + 1)가 true를 반환하는 경우 true를 반환합니다.

    • 마침표가 아니라면 x := s[index]로 두고, 해당 자식 노드가 존재하면서 check()가 true를 반환할 때 true를 반환합니다.

    • 모든 조건을 만족하지 못하면 false를 반환합니다.

  4. search() 메서드에서는 curr := head로 설정한 뒤 check(curr, word, 0)의 결과를 그대로 반환합니다.

C++ 구현 예제

아래 구현 예제를 통해 좀 더 명확하게 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
struct Node{
    bool isEnd;
    map <char, Node*> child;
    Node(){
        isEnd = false;
    }
};
class WordDictionary {
    public:
    Node* head;
    WordDictionary() {
        head = new Node();
    }
    void insertNode(Node* head, string s){
        Node* curr = head;
        int n = s.size();
        for(int i = 0; i < n; i++){
            char x = s[i];
            if(!curr->child[x]){
                curr->child[x] = new Node();
            }
            curr = curr->child[x];
        }
        curr->isEnd = true;
    }
    void addWord(string word) {
        insertNode(head, word);
    }
    bool check(Node* curr, string s, int idx = 0){
        if(idx == s.size()) return curr->isEnd;
        bool ok = false;
        if(s[idx] == '.'){
            for(int i = 0; i < 26; i++){
                char x = 'a' + i;
                if(curr->child[x] && check(curr->child[x], s, idx + 1))return true;
            }
        } else {
            char x = s[idx];
            if(curr->child[x] && check(curr->child[x], s, idx + 1))return true;
        }
        return false;
    }
    bool search(string word) {
        Node* curr = head;
        return check(curr, word);
    }
};
main(){
    WordDictionary ob;
    ob.addWord("bad");
    ob.addWord("dad");
    ob.addWord("mad");
    cout << (ob.search("pad")) << endl;
    cout << (ob.search("bad")) << endl;
    cout << (ob.search(".ad")) << endl;
    cout << (ob.search("b..")) << endl;
}

입력

WordDictionary 객체를 초기화한 뒤, main() 함수에서와 같이
addWord() 메서드와 search() 메서드를 호출합니다.

출력

0
1
1
1

출력 결과를 해석해 보면, search("pad")는 저장된 단어 중 일치하는 것이 없으므로 false(0)를 반환하고, search("bad"), search(".ad"), search("b..")는 모두 일치하는 단어를 찾았으므로 true(1)를 반환합니다.

시간 복잡도 분석

  • addWord(word): 단어의 길이를 L이라 할 때, 각 문자를 순회하며 노드를 생성하므로 시간 복잡도는 O(L)입니다.

  • search(word): 일반 문자 검색은 O(L)이지만, 마침표(.)가 포함된 경우 각 위치에서 최대 26개의 자식 노드를 모두 탐색해야 하므로 최악의 경우 O(26^L)까지 증가할 수 있습니다.

이처럼 트라이 기반 설계는 단어 삽입에는 매우 효율적이며, 와일드카드 검색에서는 백트래킹 방식의 재귀 탐색으로 유연하게 대응할 수 있다는 장점이 있습니다.