[19585]번 팀 이름 정하기

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

풀이

이 문제는 주어진 팀 이름이 사전에 정의된 ‘색상’과 ‘닉네임’의 조합으로 만들어질 수 있는지 확인하는 문제입니다.

처음에는 각 문자열 목록을 unordered_set에 저장하여 문제를 해결하고자 했습니다. 이 접근 방식은 다음과 같습니다.

해시셋(unordered_set) 접근 방식:

1. 모든 색상 이름을 unordered_set<string>에 저장합니다.
2. 모든 닉네임 이름을 별도의 unordered_set<string>에 저장합니다.
3. 각 팀 이름에 대해, 문자열을 나눌 수 있는 모든 지점 i를 기준으로 team.substr(0, i) (색상 후보)와 team.substr(i) (닉네임 후보)로 분리합니다.
4. 분리된 두 부분 문자열이 각각 색상 unordered_set과 닉네임 unordered_set에 모두 존재하는지 확인합니다.
5. 하나라도 조건을 만족하면 “Yes”를 출력하고, 모든 분할 지점을 확인해도 찾지 못하면 “No”를 출력합니다.

이 방식의 시간 복잡도는 쿼리 수 $Q$, 팀 이름 최대 길이 $L$에 대해 $O(Q \cdot L^2)$ 입니다. 각 쿼리마다 $L-1$개의 분할을 시도하고, 각 분할에서 substr 연산과 해시셋 조회가 $O(L)$의 시간이 소요되기 때문입니다.

하지만 이 방법으로 코드를 제출했을 때 메모리 초과가 발생했습니다.

코드

19585.cpp

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int C, N, Q;
    cin >> C >> N;
    unordered_set<string> colors(C), nicknames(N);
    string temp;
    while(C--){
        cin >> temp;
        colors.insert(temp);
    }
    while(N--){
        cin >> temp;
        nicknames.insert(temp);
    }
    cin >> Q;
    string team;
    while(Q--){
        bool isFind = false;
        cin >> team;
        for(int i = 0;i<team.size();i++){
            string c = team.substr(0, i);
            string n = team.substr(i, team.size() - i);
            if(colors.find(c) != colors.end() && nicknames.find(n) != nicknames.end()){
                cout << "Yes\n";
                isFind = true;
                break;
            }
        }
        if(!isFind)
            cout << "No\n";
    }
    return 0;
}

Standard Input (stdin): 2 2 red blue coder hacker 4 redcoder bluehacker whitecoder redhacker

⏳ Running... C++

최적화

메모리 초과 원인 분석

unordered_set<string>을 사용한 접근법에서 메모리 초과가 발생한 이유는, unordered_set이 내부적으로 모든 문자열 데이터를 개별적으로 저장하기 때문입니다. 문제의 제약 조건에서 색상과 닉네임의 개수는 각각 최대 100,000개이며, 각 문자열의 길이도 최대 1,000에 달할 수 있습니다. 이로 인해 수많은 문자열들이 메모리에 적재되면서 할당된 메모리 한도를 초과하게 된 것입니다.

예를 들어, “apple”, “apply”, “application” 이라는 문자열들이 있다면, unordered_set은 이 세 문자열을 각각 독립된 공간에 저장합니다.

트라이(Trie)를 이용한 메모리 최적화

이러한 메모리 문제를 해결하기 위해 트라이(Trie) 자료구조를 도입했습니다. 트라이는 문자열 집합을 저장하는 데 매우 효율적인 트리 기반 자료구조로, 공통된 접두사(prefix)를 공유하여 메모리 사용량을 크게 줄일 수 있습니다. 위의 예시에서 “appl”이라는 공통 접두사는 트라이 내에서 단 한 번만 저장됩니다.

최적화된 접근 방식:

1. 색상 트라이(Color Trie) 생성: 모든 색상 이름을 정방향으로 트라이에 삽입합니다.
2. 닉네임 트라이(Nickname Trie) 생성: 모든 닉네임 이름을 역방향으로 또 다른 트라이에 삽입합니다. 닉네임을 뒤집어 저장하면, 팀 이름의 끝에서부터 시작하는 부분 문자열(접미사)이 유효한 닉네임인지 $O(L)$ 시간에 확인할 수 있습니다.
3. 쿼리 처리: 각 팀 이름에 대해, a. isColor 배열을 만들어 팀 이름의 i번째 글자로 끝나는 접두사가 색상인지 (team[0...i]) 트라이를 통해 확인하고 결과를 저장합니다. b. isNick 배열을 만들어 팀 이름의 j번째 글자부터 시작하는 접미사가 닉네임인지 (team[j...end]) 역방향 닉네임 트라이를 통해 확인하고 결과를 저장합니다. c. 0부터 team.length() - 2까지 인덱스 i를 순회하며 isColor[i]와 isNick[i+1]이 모두 true인 지점이 있는지 확인합니다. 만약 존재한다면, 이는 유효한 팀 이름 조합을 찾았다는 의미입니다.

이 접근법의 시간 복잡도는 트라이 구성에 $O(\sum

S

)$, 쿼리 처리에 $O(Q \cdot L)$이 되어 훨씬 효율적입니다. 여기서 $\sum

S

$는 모든 색상과 닉네임 문자열의 길이 총합이며, 공간 복잡도 또한 트라이 노드의 수에 비례하여 $O(\sum

S

)$ 수준으로 최적화됩니다.

최적화된 코드

19585_optimize.cpp

#include <bits/stdc++.h>
using namespace std;
class Trie {
public:
    vector<pair<char, unique_ptr<Trie>>> child;
    bool isEOW;
    Trie() {
        isEOW = false;
    }
    Trie* findChild(char ch){
        for(const auto& p: child){
            if(p.first == ch)
                return p.second.get();
        }
        return nullptr;
    }
};
void insert(Trie* root, const string& key){
    auto crawl = root;
    for(const char ch: key){
        auto next = crawl->findChild(ch);
        if(next == nullptr){
            crawl->child.emplace_back(ch, make_unique<Trie>());
            next = crawl->child.back().second.get();
        }
        crawl = next;
    }
    crawl->isEOW = true;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int C, N;
    cin >> C >> N;
    auto colors = make_unique<Trie>();
    string color;
    while(C--){
        cin >> color;
        insert(colors.get(), color);
    }
    auto nicknames = make_unique<Trie>();
    string nickname;
    while(N--){
        cin >> nickname;
        reverse(nickname.begin(), nickname.end());
        insert(nicknames.get(), nickname);
    }
    int Q;
    cin >> Q;
    string team;
    while(Q--){
        cin >> team;
        int len = team.length();
        auto isColor = vector(len, false);
        auto crawl = colors.get();
        for(int i = 0;i<len;i++){
            const auto ch = team[i];
            crawl = crawl->findChild(ch);
            if(crawl == nullptr)
                break;
            if(crawl->isEOW)
                isColor[i] = true;
        }
        auto isNick = vector(len, false);
        crawl = nicknames.get();
        for(int i = len-1;i>=0;i--){
            const auto ch = team[i];
            crawl = crawl->findChild(ch);
            if(crawl == nullptr)
                break;
            if(crawl->isEOW)
                isNick[i] = true;
        }
        bool isFind = false;
        for(int i = 0;i<len-1;i++){
            if(isColor[i] && isNick[i+1]){
                isFind = true;
                break;
            }
        }
        if(isFind)
            cout << "Yes\n";
        else
            cout << "No\n";
    }
    return 0;
}

Standard Input (stdin): 2 2 red blue coder hacker 4 redcoder bluehacker whitecoder redhacker

⏳ Running... C++