글 읽기 - 본 문제의 시간제한, 메모리제한에 대해서 질문이 있습니다. (스포 있음)

ababc1005 2년 전 0

기본적으로

색상과 이름 모두 트라이로 저장,

트라이 구조는 vector로 구현 (없을 때마다 추가로 push_back)

해서 구현하니까 시간초과가 나더라구요.

그래서 2가지 곁다리 최적화를 해서 결국 AC를 받기는 했는데 개인적으로 좀 구차한 방법이라 문제 의도가 이게 맞나...? 싶네요

1. string을 잘라가며(substr 등 사용시 string 복사에 시간 소요) 다음 노드로 전달하지 않고 main함수에 저장된 주소값을 불러오고, index를 +1 해가며 다음 노드로 전달 -> 생각보다 여기서 절약되는 시간이 매우 크더군요.. 이것도 시간초과가 나서 2번도 넣었습니다.

2. trie에 저장된 max길이를 기억해 두었다가 그걸 넘으면 애초에 검색을 시도도 안함. -> 팀네임 길이가 2000자, 각 색상/닉네임 길이가 1000자라 쓸데없는 연산이 꽤 있거나 이를 노린 TC가 있을 것 같아 짧은 조건문 넣어보니까 바로 통과가 되었습니다.

이런 구차한 방법 안 사용하고 풀 수 있도록 시도해본 방법에는,

1. vector 대신 map을 사용한 trie -> 깔끔하게 메모리 초과

2. unordered_set<string>로 N(1)에 검색 -> 메모리 초과

이 두 가지가 있습니다.

제 짧은 지식으로는 unordered_set은 기본적으로 hash와 비슷한 형태라고 들었는데 왜 메모리 초과가 나는지는 잘 모르겠네요 ㅠㅠ

이 외에 더 깔끔한 풀이가 뭐가 있는지, 혹은 예상되는 기존 방법들이 실패했던 이유가 뭐가 있을지 가르쳐주시거나

각자 사용했던 방법 공유해주시면 성장에 큰 도움이 될 것 같습니다!

이것저것 시도하느라 정답코드는 매우 지저분하긴 한데.. 일단 이것도 업로드 합니다:)

#include<iostream>
#include<vector>
#include<string>

using namespace std;
int nMaxL = 0;
int cMaxL = 0;

class Trie{
    public:
        char value;
        vector<Trie*> next;
        bool end;

        Trie(char v){value = v; end = false;}

        void Add(string &s, int index){
            Trie* target = NULL;
            for(int i = 0; i < next.size(); i ++){
                if(s[index] == next[i] -> value){
                    target = next[i];
                    break;
                }
            }
            if(target == NULL){
                target = new Trie(s[index]);
                next.push_back(target);
            }

            if(s.length() > index + 1) target -> Add(s, index + 1);
            else target -> end = true;
        }

        bool Find(string &s, int index){
            Trie* target = NULL;
            for(int i = 0; i < next.size(); i ++){
                if(s[index] == next[i] -> value){
                    target = next[i];
                    break;
                }
            }
            if(target == NULL) return false;
            if(s.length() > index + 1) return target -> Find(s, index + 1);
            else return target -> end;
        }

        bool Find2(string &s, int index, Trie &trie){
            bool ans = false;
            if(end && s.length() - index <= nMaxL) ans = trie.Find(s, index);
            if(!ans){
                Trie* target = NULL;
                for(int i = 0; i < next.size(); i ++){
                    if(s[index] == next[i] -> value){
                        target = next[i];
                        break;
                    }
                }
                if(target != NULL && s.length() > index + 1){
                    ans = target -> Find2(s, index + 1, trie);
                }
            }
            return ans;
        }

};

Trie color('0');
Trie name('0');
string tmp;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M;
    cin >> N >> M;
    cin.ignore();


    for(int i = 0; i < N; i ++){
        getline(cin, tmp);
        color.Add(tmp, 0);
        if(cMaxL < tmp.length()) cMaxL = tmp.length();
    }

    for(int i = 0; i < M; i ++){
        getline(cin, tmp);
        name.Add(tmp, 0);
        if(nMaxL < tmp.length()) nMaxL = tmp.length();
    }

    int Q;
    cin >> Q;
    cin.ignore();

    for(int i = 0; i < Q; i ++){
        getline(cin, tmp);
        if(color.Find2(tmp, 0, name)) cout << "Yes\n";
        else cout << "No\n";
    }

    return 0;
}

djs100201 2년 전 3

저는 trie일절 안쓰고 해싱 + 해싱 했습니다.

dustkd1004 2년 전 1

일단 저는 color, name 두개 모두 map을 활용한 trie로 구현했습니다.

child 구현 방식은 포인터배열, STL map 활용 2가지로 알고 있습니다.

포인터배열은 자식에 빨리 접근할 수 있지만 메모리 사용이 많고

map은 비교적 메모리를 적게 사용하는 반면 탐색효율이 상대적으로 안좋아지는 것이죠.

map을 활용한 trie 구현이 왜 메모리초과가 발생하는 지 한번 다시 확인해보시는 것도 좋아보이네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

본 문제의 시간제한, 메모리제한에 대해서 질문이 있습니다. (스포 있음)

ababc1005 2년 전 0

djs100201 2년 전 3

dustkd1004 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말