[프로그래머스] 60060 가사 검색 (C/C++)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/60060

풀이

검색, 탐색에 관한 문제. 애초에 문제 이름에 '검색'이 들어가 있다. 검색, 탐색에 관한 문제는 보통 트리(Tree) 자료구조로 접근하는 경우가 많다.

예를 들어,

가장 널리 알려진 이진 탐색 트리(BST)를 비롯해, 균형 이진 탐색 트리(AVL), Red-Black Tree
데이터베이스 및 파일시스템 인덱스 표준으로 사용되는 B-Tree
문자열 및 접두사 검색, 자동 완성 및 와일드카드 처리에 강한 Trie(프리픽스 트리)
우선 순위 탐색, 최단 경로 탐색 등에 쓰이는 Heap(힙)
이웃 탐색에 사용되는 KD-Tree, KNN 질의
공간 데이터 인덱싱에 쓰이는 R-Tree

등이 있다.

이 문제에서는 문자열 탐색이 필요하므로 Trie 자료구조를 사용했다. 처음에는 질의에 와일드카드 문자가 포함되어 있어서, Trie 구조로 어떻게 처리할지 고민이 많았다. 하지만 문제를 자세히 읽어보니 와일드카드 문자가 접두사에만 붙는 경우와 접미사에만 붙는 경우로 제한되어 있어 생각보다 어렵지 않게 해결할 수 있었다.

보통 널리 사용되는 트리는 트리의 특성을 최대한 살린 균형 잡힌 트리다. 높이에 대한 최적화가 곧 탐색에 대한 최적화이기 때문이다. 평소 이런 트리를 구현할 때는 트리와 노드 특성을 한껏 살린 재귀적 구현을 선호한다. 하지만 이번 문제에서 구현하는 Trie는 균형이 잡혀 있지 않은 트리이므로, 효율성을 위해 재귀적 구현보다는 반복적 구현이 더 적합하다고 판단했다.

+) 와일드카드가 없는 질의에 대해서도 처리하기 위해 고민했는데, 이 글을 작성하면서 문제를 다시 읽어보니 와일드카드가 없는 질의가 들어오지 않는다고 하네,,

소스 코드

C++17

#include <bits/stdc++.h>

struct Node {
    size_t __sz = 0;
    std::unordered_map<size_t, size_t> __length;
    std::unordered_map<char, std::shared_ptr<Node>> __children;
};

struct Trie {
    std::shared_ptr<Node> root = std::make_shared<Node>();

    int insert(const std::string &word) {
        std::shared_ptr<Node> current = root;

        for (size_t i = 0; i < word.size(); i++) {
            ++current->__sz;
            ++current->__length[word.size() - i];
            if (!current->__children[word[i]]) {
                current->__children[word[i]] = std::make_shared<Node>();
            }
            current = current->__children[word[i]];
        }

        return 0;
    }

    int find(const std::string &query) const {
        std::shared_ptr<Node> current = root;

        for (size_t i = 0; i < query.size(); i++) {
            if (query[i] == '?') {
                return current->__length[query.size() - i];
            }
            if (!current->__children[query[i]]) {
                return 0;
            }
            current = current->__children[query[i]];
        }

        return current->__sz;
    };
};

std::vector<int> solution(std::vector<std::string> words, std::vector<std::string> queries) {
    std::vector<int> answer;
    Trie prefix, suffix;

    for (const auto &word: words) {
        prefix.insert(word);
        suffix.insert(std::string(word.rbegin(), word.rend()));
    }

    for (const auto &query: queries) {
        if (query.back() == '?') {
            answer.push_back(prefix.find(query));
        } else {
            answer.push_back(suffix.find(std::string(query.rbegin(), query.rend())));
        }
    }

    return answer;
}

[프로그래머스] 60060 가사 검색 (C/C++)

문제

풀이

소스 코드

Share this post