글 읽기 - [C] 시간초과

rndrnjs2003 6년 전 0

어느 부분에서 시간초과가 났는지 모르겠습니다.

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

typedef struct tagNode {
	int Data;
	struct tagNode* NextNode;
}Node;

typedef struct tagStack {
	Node* List;
	Node* Top;
}_Stack;

void CreateStack(_Stack** Stack);
void DestoryStack(_Stack* Stack);
Node* CreateNode(_Stack* Stack, int NewData);
void DestroyNode(Node* _Node);
int Top(_Stack* Stack);
void Push(_Stack* Stack, Node* NewNode);
Node* Pop(_Stack* Stack);
int IsEmpty(_Stack* Stack);
int Test(int input[],int n); /* n : 배열의 크기 */

int main(void) {
	int* input = NULL;
	int arrSize;
	int a = 0;
	Node* BufNode = NULL;
	_Stack* Stack;
	CreateStack(&Stack);

	scanf("%d", &arrSize);
	input = (int*)malloc(sizeof(int)*arrSize); 
	for (int i = 0; i < arrSize; i++) {
		scanf("%d", &input[i]);
	}
	if (!Test(input, arrSize)) {
		for (int j = 0; j < arrSize; j++) {
			while (Top(Stack) != input[j]) {
				Push(Stack, CreateNode(Stack, a));
				printf("+\n");
				a++;
			}
			BufNode = Pop(Stack);
			printf("-\n");
		}
	}
	return 0;
}


Node* CreateNode(_Stack* Stack, int NewData) {
	Node* NewNode = (Node*)malloc(sizeof(Node));
	NewNode->Data = (int*)malloc(sizeof(NewData));

	NewNode->Data = NewData;
	NewNode->NextNode = NULL;

	return NewNode;
}

void DestroyNode(Node* _Node) {
	free(_Node->Data);
	free(_Node);
}

void CreateStack(_Stack** Stack) {
	(*Stack) = (_Stack*)malloc(sizeof(_Stack));

	(*Stack)->List = NULL;
	(*Stack)->Top = NULL;
}

void DestoryStack(_Stack* Stack) {
	
	while (!IsEmpty(Stack)) {
		Node* Popped = Pop(Stack);

		DestroyNode(Popped);
	}
	free(Stack);
}


int Top(_Stack* Stack) {
	if (!IsEmpty(Stack))
		return Stack->Top->Data;
	else
		return 0;
}

void Push(_Stack* Stack, Node* NewNode) {
	if (Stack->List == NULL) {
		Stack->List = NewNode;
	}
	
	else {
		Node* Top = Stack->Top;
		Top->NextNode = NewNode;
	}
	Stack->Top = NewNode;
}

Node* Pop(_Stack* Stack) {
	Node* Popped = Stack->Top;

	if (Stack->List == Stack->Top) {
		Stack->List = NULL;
		Stack->Top = NULL;
	}
	else {
		Node* OldTop = Stack->List;
		while (OldTop->NextNode != Stack->Top) {
			OldTop = OldTop->NextNode;
		}
		OldTop->NextNode = NULL;
		Stack->Top = OldTop;
	}
	return Popped;
}

int IsEmpty(_Stack* Stack) {
	if (Stack->List == NULL)
		return 1;
	else
		return 0;
}

int Test(int input[], int n) {
	for (int i = 0; i + 2 < n; i++) {
		if (input[i] > input[i + 1] && input[i] > input[i + 2]) {
			if (input[i + 1] < input[i + 2]) {
				printf("NO\n");
				return 1;
			}
			
		}
	}
	return 0;
}

rndrnjs2003 6년 전 0

test함수가 잘못됐다는 말씀이시군요!! 감사합니다.

혹시 좋은 코드로 바꿀수 있는 방법 여쭤봐도 될까요??

djm03178 6년 전 1

아까 달았던 댓글은 제가 잘못 생각한 것 같습니다. 하지만 Test 함수가 잘못된 건 맞네요.

는 NO가 나와야 하는데 무한루프를 돕니다.

djm03178 6년 전 1

이 문제는 NO를 검사하는 코드와 답을 찾아내는 코드를 분리하는 것보다 답을 찾아내는 중에 불가능한지의 여부를 알아내는 것이 낫습니다. 배열의 앞뒤 원소만으로 검사할 수 없다고 생각합니다.

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

문제

문제

출처

ICPC

[C] 시간초과

rndrnjs2003 6년 전 0

rndrnjs2003 6년 전 0

djm03178 6년 전 1

djm03178 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말