글 읽기 - c++ 질문 드립니다. 48퍼 시간 초과

hena_42 2년 전 0

여러번 erase로 실행했을때 48퍼쯤 시간초과가 나서 이 방식으로는 풀지 못할거라고 생각은 하고 있습니다만, 그 이유가 궁금합니다.

애초에 스택 문제여서 스택으로 도전해볼거 같습니다.

코린이에게 도움을 주시면 감사하겠습니다.

#include <bits/stdc++.h>
using namespace std;
#define FORD(I, S, E) for(int I = S ; I < E ; ++I)
vector<char> v;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string a, b;   
    cin >> a >> b;

    int bsize = b.size();
    for (int i = 0 ; i< a.size()  ; ++i)
    {
        bool flag = true;
        for (int j = 0 ; j < bsize  ; ++j)
        {
            if (a[i + j] != b[j])
            {
                flag = false;
                break;
            }
            
        }
        // cout << "index: " << i <<" str[i]: " << a[i]  << " flag: " << flag <<'\n';
        
        if (flag)
            a.erase(i, bsize);
            // cout <<'\n' <<i - bsize << '\n';
            if (i - bsize - 1 >= 0)
                i = i - bsize - 1;
            else
                i = -1;
        }
        // FORD(k, 0 , v.size()) cout << v[k] <<' ';
        
    }
    if (a.size())
        cout << a <<'\n';
    else
        cout <<"FRULA\n";
    
    return 0;
}

djm03178 2년 전 0

코드를 본문에 넣었다가 다시 복사하면 지금처럼 코드가 깨집니다. 깨지지 않게 한 번에 코드 올리는 칸에 올려주세요,

hena_42 2년 전 0

코드가 깨졌었네요... 다음부터는 제대로 올리겠습니다

djm03178 2년 전 1

vector의 임의의 위치의 원소를 erase하면 그 뒤의 모든 원소들이 전부 앞으로 한 칸씩 당겨져 매우 느립니다.

hena_42 2년 전 0

string도 앞으로 당기는 방식이군요. O(N)씩 들어가겠네요. 감사합니다

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

문제

문제

출처

ICPC

c++ 질문 드립니다. 48퍼 시간 초과

hena_42 2년 전 0

djm03178 2년 전 0

hena_42 2년 전 0

djm03178 2년 전 1

hena_42 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말