3093. Longest Common Suffix Queries

https://leetcode.com/problems/longest-common-suffix-queries/

• 내가 푼 방법

문제 요약

wordsContainer 안에 있는 단어들 중에서, wordsQuery[i] 의 suffix(접미사) 와 가장 길게 일치하는 단어의 인덱스를 구하는 문제다.

동률(가장 긴 suffix 길이가 같을 때) 처리 규칙:
1. 길이가 더 짧은 단어
2. 그래도 같으면 인덱스가 더 작은 단어

핵심 아이디어

"suffix 일치" 가 키워드인데, 트라이는 보통 prefix 일치에 최적화된 자료구조다.

그럼 뒤집어서 생각하자. 단어를 뒤에서부터 앞으로 트라이에 넣으면, 원래의 suffix 가 사실상 prefix 가 된다.

예: "abcde" 를 거꾸로 "e" -> "d" -> "c" -> "b" -> "a" 순서로 트라이에 삽입.

그 다음 쿼리도 똑같이 뒤에서부터 따라 내려간다. 막힌 지점이 곧 "가장 긴 공통 suffix" 의 끝.

단계

1. makeTree — 역방향 삽입

각 단어를 마지막 인덱스부터 0까지 거꾸로 가며 트라이에 노드를 만든다.

void makeTree(Node& cur, int index, string& s, int wordIndex)
{
    if (index < 0) {
        if (cur.answer == -1) {
            cur.answer = wordIndex;
        }
        return;
    }

    char nowC = s[index];

    if (cur.child.find(nowC) == cur.child.end()) {
        cur.child[nowC] = Node(nowC, -1);
    }

    makeTree(cur.child[nowC], index - 1, s, wordIndex);
}

단어 끝에 도달했을 때 cur.answer = wordIndex 로 마킹. 같은 단어가 이미 있었으면 (먼저 들어온 인덱스가 작으니) 덮지 않는다.

2. fillAnswer — 각 노드의 최선 답 사전계산

쿼리는 결국 "이 노드까지 일치했으면 누가 답인가?" 라서, 각 노드마다 최적의 wordIndex 를 미리 채워둔다.

dfs 로 내려가며 자식들의 답을 모은 뒤:

• 그 후보들 중 가장 짧은 길이의 단어
• 동률이면 가장 작은 인덱스

int fillAnswer(Node& cur)
{
    vi candidate;

    for (auto& [key, value] : cur.child) {
        candidate.push_back(fillAnswer(value));
    }

    if (cur.answer != -1) {
        return cur.answer;
    }

    int minLength = 1e9;
    int minIndex = 1e9;

    for (auto& v : candidate) {
        minLength = min(minLength, (int)words[v].size());
    }

    vector<int> minLengthStrings;
    for (auto& v : candidate) {
        if (words[v].size() == minLength) {
            minIndex = min(minIndex, v);
            minLengthStrings.push_back(v);
        }
    }

    if (minLengthStrings.size() == 1) {
        cur.answer = minLengthStrings[0];
        return minLengthStrings[0];
    }
    cur.answer = minIndex;
    return minIndex;
}

⚠️ 함정 메모: 처음에 minIndex = min(minIndex, v) 를 첫 번째 loop 에 넣었더니, 길이 조건을 무시한 채 전체 candidate 의 최소 인덱스가 잡혔다. 그래서 query "b" 에서 길이 5짜리 dccab (idx 15) 대신 길이 9짜리 ccdcbcddb (idx 9) 가 답으로 나왔다. minIndex 갱신은 반드시 minLength 매칭 단계 안에서만 해야 한다.

3. query — suffix 따라 내려가며 가장 깊은 일치 노드의 답 반환

int query(Node& cur, int index, string& s)
{
    if (index < 0) {
        return cur.answer;
    }

    char nowC = s[index];

    if (cur.child.find(nowC) == cur.child.end()) {
        return cur.answer;
    }

    return query(cur.child[nowC], index - 1, s);
}

쿼리도 makeTree 와 똑같이 끝에서 앞으로 가며 따라 내려간다. 자식이 없으면 그 노드의 사전계산된 answer 반환.

전체 코드

class Solution
{
public:

    typedef vector<int>vi;
    typedef vector<vi>vii;
    struct Node
    {
        char c;
        map<char, Node> child;
        int answer;

        Node() = default;

        Node(char c_, int a) : c(c_), child(), answer(a)
        {
        }
    };

    vector<string> words;
    int n;
    Node root = {'r',-1};

    void makeTree(Node& cur, int index, string& s, int wordIndex)
    {
        if (index < 0)
        {
            if (cur.answer == -1) {
                cur.answer = wordIndex;
            }
            return;
        }

        char nowC = s[index];

        if (cur.child.find(nowC) == cur.child.end())
        {
            cur.child[nowC] = Node(nowC, -1);
        }

        makeTree(cur.child[nowC], index - 1, s, wordIndex);
    }

    int query(Node& cur, int index, string& s)
    {
        if (index < 0) {
            return cur.answer;
        }

        char nowC = s[index];

        if (cur.child.find(nowC) == cur.child.end())
        {
            return cur.answer;
        }

        return query(cur.child[nowC], index - 1, s);
    }

    int fillAnswer(Node& cur)
    {
        vi candidate;

        for (auto& [key, value] : cur.child)
        {
            candidate.push_back(fillAnswer(value));
        }

        if (cur.answer != -1) {
            return cur.answer;
        }

        int minLength = 1e9;
        int minIndex = 1e9;

        for (auto& v : candidate)
        {
            minLength = min(minLength, (int)words[v].size());
        }

        vector<int> minLengthStrings;
        for (auto& v : candidate)
        {
            if (words[v].size() == minLength)
            {
                minIndex = min(minIndex, v);
                minLengthStrings.push_back(v);
            }
        }

        if (minLengthStrings.size() == 1)
        {
            cur.answer = minLengthStrings[0];
            return minLengthStrings[0];
        }
        cur.answer = minIndex;
        return minIndex;
    }

    vector<int> stringIndices(vector<string>& wordsContainer, vector<string>& wordsQuery)
    {
        words = wordsContainer;
        n = wordsContainer.size();
        for (int i = 0; i < n; i++)
        {
            makeTree(root, (int)words[i].size() - 1, words[i], i);
        }

        fillAnswer(root);

        vi answer;
        for (int i = 0; i < wordsQuery.size(); i++)
        {
            int queryAnswer = query(root, (int)wordsQuery[i].size() - 1, wordsQuery[i]);
            answer.push_back(queryAnswer);
        }
        return answer;
    }
};

시간복잡도

• makeTree: 모든 단어 길이의 합 O(Σ|wordsContainer[i]|)
• fillAnswer: 트라이의 총 노드 수 O(N)
• query: 쿼리 한 개당 O(|wordsQuery[i]|), 전체 O(Σ|wordsQuery[i]|)

삽질 메모

1. Node(nowC, -1) 가 처음에 컴파일 안 됐다. 처음엔 Node 의 생성자를 정의하지 않고 Node(nowC, {}, index) 처럼 paren 으로 부르려 했는데, Node 가 aggregate 라서 paren 호출 불가 (C++17 이하). 두 가지 선택지:

   • 생성자를 추가 → paren 호출 가능
   • Node{nowC, {}, index} 처럼 brace 초기화

   나는 생성자를 추가하는 쪽 (Node(char c_, int a)) 으로 갔다.

2. minIndex 동률 처리 버그. 위에 적은 그 함정. 길이 조건을 거치지 않은 minIndex 를 쓰면 안 된다.

3. std::map<char, Node> 메모리 함정. 이 풀이는 노드마다 std::map 을 들고 있어서 RB-tree 노드 alloc 이 매번 일어난다. 알파벳이 26개로 작은 경우엔 int child[26] + node pool (vector + index) 패턴이 캐시 친화적이고 훨씬 빠르다. C++ 에서 TLE 가 빡빡하게 나오면 이쪽으로 전환 고려.

마무리

뒤집어 생각하는 게 이 문제의 전부였다. "suffix = 뒤집은 prefix" 라는 한 줄을 떠올린 순간 풀이 구조가 자동으로 나왔다. 트라이 문제는 prefix 만 다루는 게 아니라, 방향만 뒤집어도 suffix 문제로 확장된다는 걸 기억해 두면 좋겠다.