글 읽기 - 시간초과 사유를 모르겠습니다.

hyun1002 1년 전 0

제 생각에는 분명 원래 문자열의 문자열 폭탄을 제거하는 코드의 시간복잡도가 O(N)이 나올거라고 예상하는데, 혹시 다른 이유로 시간초과가 되는것일까요?

#include <iostream>
#include <string>
/*#include <cassert>
#include <cctype>
#include <set>
#include <list>
#include <deque>
#include <map>
#include <cmath>
#include <set>
#include <tuple>
#include <queue>
#include <vector>
*/
#include <stack>
#include <algorithm>

#define symbol first
#define state second

using namespace std;

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

    string str, bomb;

    cin >> str >> bomb;

    stack<pair<char, int>> S; //{symbol, state}, state는 기본적으로 0
    //state = k이면 이전에 bomb[0]~bomb[k - 1]이 연속해서 입력됐었음을 나타냄
    int size = str.length();
    int bomb_size = bomb.length();

    for(int i = 0; i < size; i++) {
        if(!S.empty()) {
            pair<char, int> curTop = S.top();//
            if(str[i] == bomb[curTop.state] && curTop.state != 0) { 
                S.pop();     //symbol의 bomb[0]~bomb[k-1]을 bomb[k]로 갱신하는 과정 
                if(curTop.state + 1 != bomb_size) {//bomb가 모두 입력됐는가?
                    S.push({str[i], curTop.state + 1});//아니라면 새로 갱신
                }            //맞다면 스택에서 제거만 하고 넘어감
            }
            else {
                if(str[i] == bomb[0]) {
                    if(bomb_size != 1)
                        S.push({str[i], 1});
                }
                else
                    S.push({str[i], 0});
            }
        }
        else {
            if(str[i] == bomb[0]) {
                if(bomb_size != 1)
                    S.push({str[i], 1});
            }
            else
                S.push({str[i], 0});
        }
    }

    string ans = "\n";

    if(!S.empty()) {
        while(!S.empty()) {
            pair<char, int> curTop = S.top(); S.pop();
            if(curTop.state > 0) {
                for(int i = curTop.state - 1; i >= 0; i--) {
                    ans = bomb[i] + ans;
                }
            }
            else {
                ans = curTop.symbol + ans;
            }
        }
    }
    else ans = "FRULA";

    cout << ans;


    return 0;
}

invrtd_h 1년 전 0

ans = /* something */ + ans :: 이 부분은 std::vector에서 O(N)짜리 insert 연산을 한 번 하는 거나 마찬가지입니다. 따라서 전체 시간복잡도 O(N^2)입니다.

hyun1002 1년 전 0

답을 출력하기위한 코드에서 문제가 있었던거네요. 답변해주셔서 감사합니다...

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

문제

문제

출처

ICPC

시간초과 사유를 모르겠습니다.

hyun1002 1년 전 0

invrtd_h 1년 전 0

hyun1002 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말