글 읽기 - [C] 시간초과

rndrnjs2003 6년 전 0

시간초과가 발생합니다.

줄일 수 있는 방법 없을까요..

/*
Name : 코딩황제
Data : 20180220
Contents
Baekjoon #1874
스택 수열

input
첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다.
둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다.
물론 같은 정수가 두 번 나오는 일은 없다.

output
입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다.
push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.
*/

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

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

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

void CreateStack(_Stack** Stack);
Node* CreateNode(_Stack* Stack, int NewData);
void Push(_Stack* Stack, Node* NewNode);
Node* Pop(_Stack* Stack);

int main(void) {
	int* input = NULL;
	int arrSize;
	int a = 0;
	int ansLen = 0;
	int flag = 1;
	char ans[200001] = { 0 };
	Node* BufNode = NULL;
	_Stack* Stack;
	CreateStack(&Stack);

	scanf("%d", &arrSize);
	input = (int*)malloc(sizeof(int)*arrSize);

	for (int j = 0; j < arrSize; j++) {
		scanf("%d", &input[j]);
		while (1) {
			if (Stack->List == NULL) {
				
				Push(Stack, CreateNode(Stack, ++a));
				ans[ansLen++] = '+';
				
			}

			if (Stack->Top->Data < input[j]) {
				Push(Stack, CreateNode(Stack, ++a));
				ans[ansLen++] = '+';
				
			}

			else if (Stack->Top->Data == input[j]) {
				BufNode = Pop(Stack);
				ans[ansLen++] = '-';
				
				break;
			}

			else {
				printf("NO\n");
				flag = 0;
				break;
			}

		}
		if (!flag)
			break;
	}

	if (flag) {
		for (int i = 0; i < ansLen; i++)
			printf("%c\n", ans[i]);
	}
	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 CreateStack(_Stack** Stack) {
	(*Stack) = (_Stack*)malloc(sizeof(_Stack));

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

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;
}

cbs0615 6년 전 0

이거 컴파일되나요 ??

Node의 Data는 integer로 선언되어있는데

CreateNode 에서 동적할당을 하는 것 같습니다.

rndrnjs2003 6년 전 0

엇 수정했었는데 되돌리기할때 깜빡했네요

컴파일은 됩니다!

djm03178 6년 전 2

Pop이 문제입니다. 현재 코드에서는 Pop을 할 때 top 직전 노드에 대한 정보가 없어서 리스트 전체 순회를 통해 그 이전 노드를 찾아나서야 하는데, 이러면 다음과 같은 케이스에서 아주 많은 시간이 소요됩니다.

100000

99999

99998

......

연결 리스트로 스택을 구현할 경우, 방향을 반대로 하는 것이 좋습니다. 왜냐하면, 스택은 오로지 탑 노드에만 관심이 있기 때문에, 아래쪽에 어떤 것들이 있는지는 당장 알 필요가 전혀 없기 때문입니다. 반대 방향으로, 즉 탑 노드부터 바텀 노드로 연결되도록 하면, push, pop 연산 모두 O(1)에 수행이 가능합니다.

rndrnjs2003 6년 전 0

djm03178 님 말씀대로 더블 링크드 리스트로 바꾼 후 풀었더니 성공했습니다. 감사합니다 선생님!

/*
Name : 코딩황제
Data : 20180220
Contents
Baekjoon #1874
스택 수열

input
첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다.
둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다.
물론 같은 정수가 두 번 나오는 일은 없다.

output
입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다.
push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.
*/

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

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

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

void CreateStack(_Stack** Stack);
Node* CreateNode(_Stack* Stack, int NewData);
void Push(_Stack* Stack, Node* NewNode);
Node* Pop(_Stack* Stack);
int Top(_Stack* Stack);
int main(void) {
	int* input = NULL;
	int arrSize;
	int a = 0;
	int ansLen = 0;
	int flag = 1;
	char ans[200001] = { 0 };
	Node* BufNode = NULL;
	_Stack* Stack;
	CreateStack(&Stack);

	scanf("%d", &arrSize);
	input = (int*)malloc(sizeof(int)*arrSize);

	for (int j = 0; j < arrSize; j++) {
		scanf("%d", &input[j]);
		while (1) {
			if (Top(Stack) < input[j]) {
				Push(Stack, CreateNode(Stack, ++a));
				ans[ansLen++] = '+';

			}
			else if (Top(Stack) == input[j]) {
				BufNode = Pop(Stack);
				ans[ansLen++] = '-';

				break;
			}

			else {
				printf("NO\n");
				flag = 0;
				break;
			}

		}
		if (!flag)
			break;
	}

	if (flag) {
		for (int i = 0; i < ansLen; i++)
			printf("%c\n", ans[i]);
	}
	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;
	NewNode->PrevNode = NULL;

	return NewNode;
}


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

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

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

	else {
		Node* OldTop = Stack->Top;
		OldTop->NextNode = NewNode;
		NewNode->PrevNode = OldTop;
	}
	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->Top->PrevNode;
		OldTop->NextNode = NULL;
		Stack->Top = OldTop;
	}
	return Popped;
}
int Top(_Stack* Stack) {
	if (Stack->Top == NULL)
		return -1;
	else
		return Stack->Top->Data;
}

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

문제

문제

출처

ICPC

[C] 시간초과

rndrnjs2003 6년 전 0

cbs0615 6년 전 0

rndrnjs2003 6년 전 0

djm03178 6년 전 2

rndrnjs2003 6년 전 0

djm03178 님 말씀대로 더블 링크드 리스트로 바꾼 후 풀었더니 성공했습니다. 감사합니다 선생님!

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말