글 읽기 - 시간초과는 어떻게 해결해야할까요??

twl0812 1년 전 0

DLL을 이용한 스택을 구현했는데 시간초과가 나옵니다. 시간줄이는 방법이 있을까요??

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node{
    int data;
    struct node * prev;
    struct node * next;
}n;
n* top=0;
int size=0;
void push(int v)
{
    n* new=(n*)malloc(sizeof(n));
    new->data=v;
    new->prev=new->next=0;
    if(top==0)
    {
        top=new;
        size++;
        return;
    }
    n* cur=top;
    while(cur->prev!=0)
    {
        cur=cur->prev;
    }
    cur->prev=new;
    size++;
    new->next=cur;
    top=new;
    return;
}
int empty(void)
{
    if(top==0)
    {
        return 1;
    }
    return 0;
}
void pop(void)
{
    if(empty()==1)
    {
        printf("-1\n");
        return;
    }
    n* cur=top;
    if(cur->next==0)
    {
        printf("%d\n",top->data);
        size--;
        top=0;
        free(top);
        return;
    }
    printf("%d\n",top->data);
    size--;
    top=top->next;
    free(cur);
    return;
}

int main()
{
    int a;
       scanf("%d",&a);
       char str[10];
       for(int i=0;i<a;i++)
       {
           scanf("%s",str);
           if(!strcmp(str,"push"))
           {
               int x;
               scanf("%d",&x);
               push(x);
           }
           if(!strcmp(str,"pop"))
           {
               pop();
           }
           if(!strcmp(str,"empty"))
           {
               int k=empty();
               printf("%d\n",k);
           }
           if(!strcmp(str,"top"))
           {
               if(top==0)
               {
                   printf("-1\n");
               }
               else
               {
               printf("%d\n",top->data);
               }
           }
           if(!strcmp(str,"size"))
           {
               printf("%d\n",size);
           }
       }
}

0000000000 1년 전 0

push() 함수의 시간복잡도가 O(N)이기에 힘들어 보입니다. 일반 배열을 이용한 구현을 추천드립니다.

twl0812 1년 전 0

문제를 다시읽으니까 N이 10000이여서 10000개 배열만드니까 해결되었습니다. 감사합니다.

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

문제

문제

출처

ICPC

시간초과는 어떻게 해결해야할까요??

twl0812 1년 전 0

0000000000 1년 전 0

twl0812 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말