글 읽기 - c++ 시간초과

tinea17 3년 전 0

all 부분 구현에서 S.clear()을 삭제하면 시간초과가 되지않는데,

저 부분을 넣으면 시간초과가 뜹니다.

혹시 이유 좀 알려주실 수 있으실까요!

// 집합

#include <iostream>
#include <set>
#include <string>
using namespace std;

int m;
set<int> S;
set<int> allSet = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 };
// all 연산을 위해 1~20 set을 미리 선언

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> m;
    for (int i = 0; i < m; i++)
    {
        string s;
        cin >> s;

        int x;
        if (s == "add")
        {
            cin >> x;
            if (S.find(x) != S.end())
                continue;
            S.insert(x);
        }
        else if (s == "remove")
        {
            cin >> x;
            if (S.find(x) == S.end())
                continue;
            S.erase(x);
        }
        else if (s == "check")
        {
            cin >> x;
            if (S.find(x) != S.end())
                cout << 1 << '\n';
            else
                cout << 0 << '\n';
        }
        else if (s == "toggle")
        {
            cin >> x;
            if (S.find(x) != S.end())
                S.erase(x);
            else
                S.insert(x);
        }
        else if (s == "all")
        {
            S.clear();
            S = allSet;
        }
        else
            S.clear();
    }
}

kangwlgns 3년 전 1

set의 clear함수의 시간 복잡도가 O(n)이라 걸리는 것 같습니다.

Green55 3년 전 0

올려주신 코드에서 57라인만 지우고 그대로 내봤는데 728ms로 맞았습니다. 정말로 저 부분만만 바꾸셨나요?

tinea17 3년 전 0

@Green55 님 네 57라인만 지우면 맞고, 지우지않으면 시간초과 뜹니다!

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

문제

문제

출처

ICPC

c++ 시간초과

tinea17 3년 전 0

kangwlgns 3년 전 1

Green55 3년 전 0

tinea17 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말