글 읽기 - 1874번 C언어 시간 초과

mymoonkyu 2년 전 0

예제는 다 맞게 나오는 것 같은데, 19% 부근에서 시간 초과 나오네요..

배열을 전역변수로도 바꿔봤는데 똑같습니다.

어느 부분에서 시간을 많이 잡아먹는지 알고 싶습니다.

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100001

int seq[MAX_SIZE];
char ans[MAX_SIZE*2];

typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

void init(Stack* s) {
    s->top = -1;
}

int empty(Stack* s) {
    return (s->top == -1);
} // empty = 1, filled = 0

void push(Stack* s, int item) {
    s->data[++(s->top)] = item;
}

int pop(Stack* s) {
    if (empty(s)) {
        return -1;
    } else {
        return s->data[(s->top)--];
    }
}

int top(Stack* s) {
    return s->data[s->top];
}

int main() {
    Stack s;
    init(&s);

    int n, i, j, k;
    scanf("%d", &n);

    for (i=0; i<n; i++) {
        scanf("%d", &seq[i]);
    } // init sequence

    i = 0, j = 1, k = 0;
    while (i < n) {
        if (seq[i] > top(&s) || empty(&s)) {
            while (seq[i] > top(&s) || empty(&s)) {
                push(&s, j);
                ans[k++] = '+';
                j++;
            }
        } else {
            while (seq[i] == top(&s)) {
                if (pop(&s) == -1) {
                    printf("NO");
                    return 0;
                }
                ans[k++] = '-';
                i++;
            }
        }
    }

    i = 0;
    while (ans[i] != '\0') {
        printf("%c\n", ans[i]);
        i++;
    }

    return 0;
}

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

문제

문제

출처

ICPC

1874번 C언어 시간 초과

mymoonkyu 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말