글 읽기 - [C] 시간초과

sykim11 3년 전 0

아래 게시판의 Tip을 확인해보았습니다만, 원인을 모르겠습니다.

https://www.acmicpc.net/board/view/22447

입출력의 경우에는 scanf/printf 의 표준 입출력을 사용하고 있습니다.

알고리즘 확인해보면, 입력으로 받은 N개의 수열에 대한 for문안에 while 문이 있긴 합니다.

while 문은 최대 1~N까지만 반복되지만 N개의 수열을 확인하는 매번 N번을 도는 게 아니라 j가 N에 도달하면 더이상 증가하지 않고 탈출하거나 pop만 수행하게 됩니다. 이렇게 되면 복잡도는 O(2N)정도인 것으로 보이는데요. 8%정도에서 시간초과가 발생합니다.

stack 처리 관련하여 함수를 선언하여 구현하였으나, 함수호출로 인한 성능이 영향을 줄까 싶어서 stack 배열을 직접 핸들링하도록 수정해보았으나 시간 초과 문제가 해결되지 않습니다.

#include <stdio.h>
#include <string.h>

int N;
int a[100001];
int top=-1;
void stack_push(int n)
{
        ++top;
        a[top] = n;
//      printf("push : %d(top = %d)\n", a[top], top);
}

int stack_pop(void)
{
        if(top == -1){
//              printf("pop : -1\n");
                return -1;
        }
//      printf("pop : %d\n",  a[top]);
        return a[top--];
}

int stack_size(void)
{
        return top+1;
}

int stack_empty(void)
{
        if(top == -1)
                return 1;

        return 0;
}

int stack_top(void)
{
        if(top == -1)
                return -1;

        return a[top];
}
int main(void)
{
        int i, j, b_false;
        int arr[100000];
        char result[100000];

        scanf("%d", &N);
        if(N < 1 || N > 100000) return -1;
        j=1;
        b_false=0;

        for(i=0;i<N;i++)
        {
                scanf("%d", &arr[i]);
                if(arr[i] < 1 || arr[i] > N) return -1;

                while(top == -1 || a[top] < arr[i]){
                        a[++top] = j;
                        strcat(result, "+");
                        j++;
                        if(j>N){
                            b_false = 1;
                            break;
                        }
                }

                if(top == -1 || a[top] == arr[i]){
                        a[top--];
                        strcat(result, "-");
                }
                else {
                        b_false = 1;
                        break;
                }
        }

        if( b_false )
                printf("NO\n");
        else
        {
                for(i=0;i<strlen(result);i++){
                        printf("%c\n", result[i]);
                }
        }
}

sykim11 3년 전 0

질문 글을 올리고 나서, stcat 관련된 부분을 개선해 적용해보았습니다.

strcat 함수 대신에 result 배열의 index를 별도 관리하며 "+"/"-"를 넣었더니 pass합니다.

참고로, 위의 코드에서 line 64~68까지는 오류 코드이므로 삭제되어야 합니다.

for(i=0;i N) return -1;

while(top == -1 || a[top] < arr[i]){
a[++top] = j;
//strcat(result, "+");
result[idx++] = '+';
j++;
//if(j>N){
// b_false = 1;
// break;
//}
}

if(top == -1 || a[top] == arr[i]){
a[top--];
//strcat(result, "-");
result[idx++] = '-';
}
else {
b_false = 1;
break;
}
}

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

문제

문제

출처

ICPC

[C] 시간초과

sykim11 3년 전 0

sykim11 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말