C++ Map의 전역변수 설정여부에 따른 시간 변화

  • kwonmha
    kwonmha

    NERD2
    문제를 풀다가 코드를 책에 나온 것과 거의 동일하게 했는데
    시간 초과가 나더라고요.
    차이점이 있다면 책에는 map< int, int > coord를 전역변수로 설정했었고, 저는 메인 함수 안에다 선언하고 함수를 호출할 때마다 인자로 넘겨줬습니다.
    그래서 책에 나온 방식대로 하니 되더라고요.

    왜 이렇게 차이가 나는 건가요?
    map< int, int > coord를 인자로 넘겨주는게 시간이 그렇게 오래 걸리나요?

    코드는 아래와 같습니다.

    #include <cstdio>
    #include <map>
    
    #pragma warning(disable:4996)
    
    using namespace std;
    
    bool IsDominated(map<int, int> coords, int a, int b){
        map<int, int>::iterator cit = coords.upper_bound(a);
    
        if (cit == coords.end())
            return false;
        return b < cit->second;
    }
    
    void RemoveDominated(map<int, int> &coords, int a, int b){
        map<int, int>::iterator cit = coords.lower_bound(a);
    
        if (cit == coords.begin()) return;
        cit--;
        while (true){
            if (cit->second > b) break;
            if (cit == coords.begin()){
                coords.erase(cit);
                break;
            }
            else{
                map<int, int>::iterator cit2 = cit;
                cit2--;
                coords.erase(cit);
                cit = cit2;
            }
        }
        return;
    }
    
    int CountPpl(map<int, int> &coords, int a, int b){
    
        // 지배당하면 필요없다
        if (!IsDominated(coords, a, b)){
            // 지배하는 것들 지우기
            RemoveDominated(coords, a, b);
            //coords.insert(coords.end(), make_pair(a, b));
            coords[a] = b;
        }       
        return coords.size();
    }
    
    int main(void){
        //freopen("input.txt", "r", stdin);
        int tc, ppl;
        map<int, int> coords;
        scanf("%d", &tc);
    
        for (int i = 0; i < tc; i++){
            scanf("%d", &ppl);
            int a, b, count = 0;
            coords.clear();
            for (int j = 0; j < ppl; j++){
                scanf("%d %d", &a, &b);
                if (j == 0){
                    coords[a] = b;
                    count += 1;
                    continue;
                }
                count += CountPpl(coords, a, b);
            }
            printf("%d\n", count);
        }
    
        return 0;
    }
    

    3년 전
4개의 댓글이 있습니다.
  • VOCList
    VOCList

    IsDominated의 coords도 &로 받아보시져


    3년 전 link
  • kwonmha
    kwonmha

    오 그렇게 하니까 빠르게 풀리네요. 감사합니다.
    IsDominated에선 coords를 변경시킬 일이 없어서 쓰지 않았는데...
    시간이 걸리는 원인은 IsDominated가 호출될 때 coords를 복사해서 그런 건가요?


    3년 전 link
  • wookayin
    wookayin

    map<int, int> coords 이렇게 파라메터를 선언하시면, map 객체가 복사되어서 느립니다.

    변경시킬 일이 없다면 const map<int, int> &coords 이렇게 const로 선언하면 좋습니다.


    3년 전 link
  • kwonmha
    kwonmha

    네 답변 감사합니다!


    3년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.