C++로 구현하는 검색 제안 시스템: 접두사 기반 자동완성 알고리즘

검색 엔진이나 온라인 쇼핑몰에서 흔히 볼 수 있는 자동완성 기능은 사용자가 타이핑하는 즉시 관련 항목을 실시간으로 제안해 줍니다. 이번 글에서는 C++을 이용해 이러한 검색 제안(Search Suggestions) 시스템을 구현하는 방법을 문제 정의부터 코드 분석까지 단계별로 살펴보겠습니다.

문제 정의

문자열 배열 products와 문자열 searchWord가 주어집니다. 우리는 searchWord의 각 문자가 입력될 때마다 products 목록에서 최대 3개의 상품 이름을 제안하는 모듈을 설계해야 합니다. 제안되는 상품은 지금까지 입력된 검색어와 공통 접두사(prefix)를 가져야 하며, 조건에 맞는 상품이 3개보다 많다면 사전순으로 가장 앞선 3개를 반환해야 합니다.

예시로 이해하기

입력이 다음과 같다고 가정해 보겠습니다.

products = ["mobile", "mouse", "moneypot", "monitor", "mousepad"]
searchWord = "mouse"

이 경우 출력은 다음과 같습니다.

[["mobile", "moneypot", "monitor"],
 ["mobile", "moneypot", "monitor"],
 ["mouse", "mousepad"],
 ["mouse", "mousepad"],
 ["mouse", "mousepad"]]

"m"까지 입력했을 때는 mobile, moneypot, monitor가 사전순으로 앞서므로 이 세 상품이 선택됩니다. "mo"에서도 동일하지만, "mou"가 되는 순간 접두사가 일치하는 상품은 mouse와 mousepad뿐이므로 두 상품만 제안됩니다.

풀이 전략

이 문제는 정렬된 맵(std::map)을 활용하면 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 '접두사를 키로, 해당 접두사를 가지는 상품 목록을 값으로' 미리 저장해 두는 것입니다. 구체적인 단계는 다음과 같습니다.

키는 문자열, 값은 문자열 벡터인 맵 m을 선언합니다. C++의 std::map은 키를 자동으로 사전순으로 정렬해 주므로 결과 순서 관리가 쉬워집니다.
상품 배열 p를 사전순으로 정렬합니다.
각 상품 p[i]에 대해 모든 접두사를 생성하면서 다음을 수행합니다.
- 빈 문자열 x를 만들고, 한 글자씩 이어 붙여가며 접두사를 확장합니다.
- m[x]에 저장된 상품이 3개 미만이면 현재 상품 p[i]를 추가합니다.
결과를 담을 2차원 벡터 res를 준비하고, 임시 문자열 temp를 빈 문자열로 초기화합니다.
검색어 s의 각 문자에 대해 temp에 문자를 하나씩 추가하고, m[temp]를 res에 삽입합니다.
res를 반환합니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<vector<auto> > v){
    cout << "[";
    for(int i = 0; i < v.size(); i++){
        cout << "[";
        for(int j = 0; j < v[i].size(); j++){
            cout << v[i][j] << ", ";
        }
        cout << "],";
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& p, string s) {
        map<string, vector<string>> m;
        sort(p.begin(), p.end());
        for(int i = 0; i < p.size(); i++){
            string x = "";
            for(int j = 0; j < p[i].size(); j++){
                x += p[i][j];
                if(m[x].size() < 3) m[x].push_back(p[i]);
            }
        }
        vector<vector<string>> res;
        string temp = "";
        for(int i = 0; i < s.size(); i++){
            temp += s[i];
            res.push_back(m[temp]);
        }
        return res;
    }
};

int main(){
    vector<string> v = {"mobile","mouse","moneypot","monitor","mousepad"};
    Solution ob;
    print_vector(ob.suggestedProducts(v, "mouse"));
}

실행 결과

입력

["mobile","mouse","moneypot","monitor","mousepad"]
"mouse"

출력

[[mobile, moneypot, monitor], [mobile, moneypot, monitor], [mouse,
mousepad], [mouse, mousepad], [mouse, mousepad]]

코드 동작 원리와 성능 분석

이 알고리즘의 핵심은 전처리(preprocessing) 단계입니다. 먼저 상품 배열을 사전순으로 정렬한 뒤, 각 상품이 가질 수 있는 모든 접두사를 맵에 미리 등록합니다. 정렬이 선행되었기 때문에 각 접두사 키에는 자연스럽게 사전순으로 앞서는 상품부터 최대 3개까지만 저장됩니다. 따라서 별도의 비교 로직 없이도 '사전순 최소 3개'라는 요구 조건이 자동으로 충족됩니다.

이후 검색어가 한 글자씩 입력될 때마다 해당 접두사를 키로 조회하기만 하면 되므로 검색 단계는 매우 빠르게 처리됩니다. 상품 이름들의 총 길이를 N, 검색어 길이를 M이라 할 때 전체 시간 복잡도는 대략 O(N log N + M) 수준입니다.

참고로 이 문제는 트라이(Trie) 자료구조를 사용해서도 풀 수 있습니다. 트라이의 각 노드에 최대 3개의 제안 목록을 유지하면 메모리를 더 효율적으로 관리할 수 있어 대규모 데이터셋에 적합합니다. 다만 구현 난이도가 높아지므로, 소규모 입력에서는 위의 맵 기반 접근이 더 간결하고 실용적인 선택입니다.