글 읽기 - 시간 단축

akqjqcjs7 3년 전 0

문제는 결과적으로 해결했지만 시간이나 코드 자체가 깔끔한 것 같지 않아 질문드립니다.

1. 시간을 의미 있게 단축 시킬 수 있는 방법이 있는지 알고 싶습니다.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<memory.h>
int Start = 0, End = -1;
int N;
void push(int *Queue, int data) {
    End++;
    if (End == N) {
        End = 0;
    }
    Queue[End] = data;
    //Queue[End++] = data;
    //if(End == N) End = 0;

}
int empty(int* Queue) {
    if (Start >= End && Queue[Start] == -1) {
        return 1;
    }
    return 0;
}
int pop(int *Queue) {
    if (empty(Queue) == 1) {
        return -1;
    }
    else {
        int data = Queue[Start];
        Queue[Start++] = -1;

        if (Start == N) {
            Start = 0;
        }

        return data;
    }
}
int size(int *Queue) {
    if (Start <= End) {
        return End - Start + 1;
    }
    else {
        if (Queue[Start] == -1) {
            return 0;
        }
        else {
            return N - Start + End + 1;
        }
    }
}

int front(int *Queue) {
    if (Queue[Start] == -1) return -1;
    return Queue[Start];
}
int back(int* Queue) {
    if (Queue[End] == -1 || End == -1) return -1;
    return Queue[End];
}
int main()
{

    scanf("%d", &N);
    int* Queue = (int*)malloc(sizeof(int) * N);
    for (int i = 0; i < N; i++) {
        Queue[i] = -1;
    }
    for (int i = 0; i < N; i++) {
        char Q[6];
        scanf("%s", Q);

        if (strcmp(Q, "push") == 0) {
            int data;
            scanf("%d", &data);
            push(Queue, data);
        }
        else if (strcmp(Q, "pop") == 0) {
            printf("%d\n", pop(Queue));
        }
        else if (strcmp(Q, "size") == 0) {
            printf("%d\n", size(Queue));
        }
        else if (strcmp(Q, "empty") == 0) {
            printf("%d\n", empty(Queue));
        }
        else if (strcmp(Q, "front") == 0) {
            printf("%d\n", front(Queue));
        }
        else if (strcmp(Q, "back") == 0) {
            printf("%d\n", back(Queue));
        }
    }
    

    return 0;
}

ckdgus2482 3년 전 0

이 문제는 계산 집중적인 문제가 아니어서 입출력 시간이 대부분의 러닝타임을 잡아먹습니다.

출력의 경우 어떤 방식의 출력이든 유의미한 차이가 나기는 힘들지만 입력의 경우는 다릅니다. 러닝타임 순으로 상위권에 있는 코드들을 보면 freed등으로 상당히 큰 버퍼 단위로 읽기를 수행한 후 정수 포맷으로 직접 파싱하고 있는걸 볼 수 있습니다. 이러한 구현은 포맷 스트링을 이용한 printf 등 보다 훨씬 빠르게 동작합니다.

아마 유의미한 차이는 없을 테지만 간단하게 최적화를 좀 하자면 명령어를 판단할때 strcmp로 문자열을 비교하지 말고 이니셜만 가지고 판단하는게 더 빠르겠죠.

akqjqcjs7 3년 전 0

자세한 답변감사드립니다. 입출력에서도 시간차이가 크게 난다고 생각치 못했습니다. 감사합니다!

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

문제

문제

출처

ICPC

시간 단축

akqjqcjs7 3년 전 0

ckdgus2482 3년 전 0

akqjqcjs7 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말