글 읽기 - 시간초과가 나오는 이유를 잘 모르겠습니다. ㅠㅠ

dragonash 5년 전 0

제목 그대로 시간초과가 나는 이유를 잘 몰라서 질문글을 작성했습니다.

스택을 이용하여 코드를 작성했습니다.

도움 부탁드립니다. ㅠㅠ

#include <stdio.h>
#include <stack>
#include <string.h>
using namespace std;
char ans[600000+1];
char str[100000+1];
int main()
{
    int n;
    char o,add;
    stack <char> L;
    stack <char> R;

    scanf("%s", &str);
    for(int i=0; i<strlen(str); i++)
    {
        L.push(str[i]);
    }
    scanf("%d", &n);
    for(int i=0; i<n; i++)
    {
        scanf(" %c", &o);
        if(o == 'L')
        {
            if(!L.empty())
            {
                R.push(L.top());
                L.pop();
            }
        }
        else if(o == 'D')
        {
            if(!R.empty())
            {
                L.push(R.top());
                R.pop();
            }
        }
        else if(o == 'B')
        {
            if(!L.empty())
                L.pop();
        }
        else if(o == 'P')
        {
            scanf(" %c", &add);
            L.push(add);
        }
    }
    int temp = 0;
    while(!L.empty())
    {
        ans[temp] = L.top();
        L.pop();
        temp++;
    }
    for(int i=0; i<temp; i++)
    {
        printf("%c", ans[temp-i-1]);
    }
    while(!R.empty())
    {
        printf("%c", R.top());
        R.pop();
    }
}

djm03178 5년 전 1

15번째 줄은 루프를 한 번 돌 때마다 strlen(str)가 다시 호출됩니다. strlen은 문자열의 시작 지점부터 시작하여, 한 문자씩 보면서 널 문자가 나타날 때까지 전진합니다. 따라서 문자열의 길이에 비례하는 시간이 걸리고, 전체 루프는 O(길이^2)이 됩니다.

다음과 같이 바꿔주면 됩니다.

    int len = strlen(str);
    for(int i=0; i<len; i++)
    {
        L.push(str[i]);
    }

dragonash 5년 전 0

덕분에 해결됐습니다! 답변 진심으로 감사드립니다.

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

문제

문제

출처

ICPC

시간초과가 나오는 이유를 잘 모르겠습니다. ㅠㅠ

dragonash 5년 전 0

djm03178 5년 전 1

dragonash 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말