글 읽기 - [C] 시간 초과가 뜨내요, 도움을 부탁드립니다ㅠㅠ

bangdy 6년 전 0

이것 저것 시도도 많이 해봤는데,

자꾸 시간초과가 뜨내요..

저 알고리즘 자체도, C++로 돌아가는거 참고해서 작성한건데...

고수님들의 도움을 부탁드립니다.

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

typedef struct stack{
	int array[100000];
	int index;
} stack;

void init(stack *s){
	s->index = -1;
}

void push(stack *s, int data){
	s->array[++(s->index)] = data;
}

void pop(stack *s){
	--(s->index);
}

int return_top(stack s){
	if(s.index != -1){
		return s.array[s.index];
	}
	else{
		return -1;
	}
	
}

int is_empty(stack s){
	if(s.index == -1){
		return 1;
	}
	else{
		return 0;
	}
}


int main(void){
	int N, k = 1, c = 0, t, i;
	char b[200001];
	stack s;
	init(&s);
	
	scanf("%d",&N);
	
	while(c < 2*N){
		scanf("%d",&t);
		while(k <= t ){
			push(&s, k++);
			b[c++] = '+';
		}
		if(t != return_top(s)){
			printf("NO");
			return 0;
		}
		b[c++] = '-';
		pop(&s);
	}
	
	for(i = 0; i < c ; i++){
		printf("%c\n",b[i]);
	}
}

chogahui05 6년 전 0

알고리즘은 정말 잘 짜셨습니다. 근데 왜 시간초과가 될까요?

stack 구조체가 있습니다. 이것은 어떤 식으로 저장이 되어 있냐면요.

int형 배열 10만개, 그리고 index. 이렇게 해서 sizeof(int) * (10만 1)의 크기를 가집니다.

이걸 값 복사 하면 어떻게 될까요?

chogahui05 6년 전 0

엄밀히 따지면 c 같은 경우, 참조에 의한 호출은 없긴 하지만요.

s 자체를 그냥 넘겨버리면 이렇게 되어 버립니다.

[스택 s = 엄청나게 큰 데이터] = callee에 그대로 복사 붙여넣기 하고 가실게요~

s의 크기를 출력하는 코드를 넣어보면 알 수 있죠.

함수 호출이 되면 어떤 일이 일어날까요?

내가 넘겨준 인자들을 사아앜~ 복사해서, 쌓아놓습니다. 리턴 주소와 함께 말이죠. (이건 caller에 돌아가기 위해서 쓰는 거라 조금 중요해요)

스택. 통째로 넘기면 얼마나 걸릴까요? 물론 스택 포인터야. 넘긴만큼 빼야지~!! 이렇게 퉁칠 수 있겠지만..

int형 배열을 통째로 10만개를 복사하는 게 문제에요. memcpy 함수 복잡도가 O(n)이지요. 시간이 많이 걸려요.

이걸 n회 반복하면? 시간 복잡도가 O(n^2)고요. 시간초과가 안 나는 게 이상한 게 아닐까요?

포인터로 넘기면 sizeof(int *) 크기만큼 복사하면 그만입니다. 그러면 시간 복잡도가 O(n)으로 줄어들겠지요.

배열과 포인터의 차이점, 스택 프레임에 대해서 알아보시는 게 어떨까요?

mendou12 6년 전 0

알고리즘은 잘 짜신 듯 해여

님 코드 클래스로 바꿔서만 해도 통과하는 걸 보니깐..;

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct stack {
	int array[100000];
	int index;
	void init() {
		index = -1;
	}

	void push(int data) {
		array[++(index)] = data;
	}

	void pop() {
		--(index);
	}

	int return_top() {
		if (index != -1) {
			return array[index];
		}
		else {
			return -1;
		}

	}

	int is_empty() {
		if (index == -1) {
			return 1;
		}
		else {
			return 0;
		}
	}
} stack;


int main(void) {
	int N, k = 1, c = 0, t, i;
	char b[200001];
	stack s;
	s.init();

	scanf("%d", &N);

	while (c < 2 * N) {
		scanf("%d", &t);
		while (k <= t) {
			s.push(k++);
			b[c++] = '+';
		}
		if (t != s.return_top()) {
			printf("NO");
			return 0;
		}
		b[c++] = '-';
		s.pop();
	}

	for (i = 0; i < c; i++) {
		printf("%c\n", b[i]);
	}
}

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

문제

문제

출처

ICPC

[C] 시간 초과가 뜨내요, 도움을 부탁드립니다ㅠㅠ

bangdy 6년 전 0

chogahui05 6년 전 0

chogahui05 6년 전 0

mendou12 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말