글 읽기 - 시간초과

20171451 3년 전 0

결과값은 제대로 나오는거같은데 왜 시간초과가 뜨는건지 궁금합니다

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define NUM_CMD 6
char *cmds[NUM_CMD] = { "push", "pop",
"size", "empty", "front", "back" };


typedef struct listNode{
           int data;
           struct listNode*next;
}listNode;
listNode*first = NULL;

int is_empty()
{
           if (first)
                     return 0;
           else
                     return   1;
}

int dequeue()
{
           listNode *tmp = first;
           if (first)
           {
                     first = first->next;
                     return tmp->data;
                     free(tmp);
           }
                     return -1;
}

void enqueue(int num)
{
           listNode *pPre = NULL;
           listNode *pLoc = first;
           listNode *pNew = (listNode *)malloc(sizeof(listNode));
           pNew->data = num;
           pNew->next = NULL;
           while (pLoc)
           {
                     pPre = pLoc;
                     pLoc = pLoc->next;
           }
           if (pPre)
                     pPre->next = pNew;
           else
                     first = pNew;
}


int peek_front()
{
           if (is_empty())
                     return -1;
           return first->data;
}

int peek_rear()
{
           listNode *pPre = NULL;
           listNode *pLoc = first;
           if (is_empty())
                     return -1;
            while (pLoc)
           {
                     pPre = pLoc;
                     pLoc = pLoc->next;
           }
           return pPre->data;         
}

int size()
{
           listNode*pLoc = first;
           int cnt = 0;
           while (pLoc)
           {
                     pLoc = pLoc->next;
                     cnt++;
           }
           return cnt;
}

int main()
{
           int N;
           char cmd[6];
           int i, num;

           scanf("%d", &N);
           while (N--)
           {
                     scanf("%s", cmd);
                     for (i = 0; i < NUM_CMD; i++)
                     {
                                if (strcmp(cmd, cmds[i]) == 0)
                                           break;
                     }

                     switch (i)
                     {
                     case 0:
                                scanf("%d", &num);
                                enqueue(num);
                                break;
                     case 1:
                                printf("%d\n", dequeue());
                                break;
                     case 2:
                                printf("%d\n", size());
                                break;
                     case 3:
                                printf("%d\n", is_empty());
                                break;
                     case 4:
                                printf("%d\n", peek_front());
                                break;
                     case 5:
                                printf("%d\n", peek_rear());
                                break;
                     default:
                                printf("wrong cmd: !%s!\n", cmd);
                                exit(1);
                     }
           }

           return 0;
}

bupjae 3년 전 0

enqueue, peek_rear, size 가 O(n) 입니다.

이 문제를 올바르게 풀기 위해서는 모든 명령어가 O(1) 에 수행되어야 합니다.

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

문제

문제

출처

ICPC

시간초과

20171451 3년 전 0

bupjae 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말