글 읽기 - C에서의 시간초과는 뭘까요?

didqhtmd 3일 전 0

https://www.acmicpc.net/proble...

질문게시판에 다른 시간초과글들 참고했을 때 이거 참고하라는 댓글이 있던데

C의 경우는 뭘까요? 다른 시간초과 글들 모두 C++인듯 싶고 C에서는 시간초과가 보통은 안 나나 본데...

이중연결리스트나 배열로 구현했어야 했나요?

//정수를 저장하는 덱을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
//
//명령은 총 여덟 가지이다.
//
//1 X: 정수 X를 덱의 앞에 넣는다. (1 ≤ X ≤ 100, 000)
//2 X : 정수 X를 덱의 뒤에 넣는다. (1 ≤ X ≤ 100, 000)
//3 : 덱에 정수가 있다면 맨 앞의 정수를 빼고 출력한다.없다면 - 1을 대신 출력한다.
//4 : 덱에 정수가 있다면 맨 뒤의 정수를 빼고 출력한다.없다면 - 1을 대신 출력한다.
//5 : 덱에 들어있는 정수의 개수를 출력한다.
//6 : 덱이 비어있으면 1, 아니면 0을 출력한다.
//7 : 덱에 정수가 있다면 맨 앞의 정수를 출력한다.없다면 - 1을 대신 출력한다.
//8 : 덱에 정수가 있다면 맨 뒤의 정수를 출력한다.없다면 - 1을 대신 출력한다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdlib.h>
#include <stdio.h>

typedef struct Deque Deque;
typedef struct Node node;
typedef node* nodeptr;
typedef node* nodeAddr;
struct Deque {
	nodeptr front;
	nodeptr back;
	int size;
};
struct Node{
	int element;
	nodeptr next;
};

nodeAddr createNode(int element);
Deque createDeque();
void push_front(int element, Deque *deque);
void push_back(int element, Deque *deque);
int pop_front(Deque* deque);
int pop_back(Deque* deque);
int size_Deque(Deque deque);
int is_empty(Deque deque);
int front(Deque deque);
int back(Deque deque);

int main() {
	int command, N;
	scanf("%d", &N);
	Deque deck = createDeque();
	for (int i = 0;i < N;i++) {
		scanf("%d", &command);

		int input;
		switch (command) {
		case 1:
			scanf("%d", &input);
			push_front(input,&deck);
			break;
		case 2:
			scanf("%d", &input);
			push_back(input, &deck);
			break;
		case 3:
			printf("%d\n", pop_front(&deck));
			break;
		case 4:
			printf("%d\n", pop_back(&deck));
			break;
		case 5:
			printf("%d\n", size_Deque(deck));
			size_Deque(deck);
			break;
		case 6:
			printf("%d\n", is_empty(deck));
			break;
		case 7:
			printf("%d\n",front(deck));
			break;
		case 8:
			printf("%d\n", back(deck));
			break;
		default:
			break;
		}
	}
}




nodeAddr createNode(int element) {
	nodeptr newnode = (nodeAddr)malloc(sizeof(node));
	newnode->element = element;
	newnode->next = NULL;
	return newnode;
}
Deque createDeque() {
	Deque* newDeck = (Deque*)malloc(sizeof(Deque));
	if (newDeck != NULL) {
		newDeck->back = NULL;
		newDeck->front = NULL;
		newDeck->size = 0;
	}
	else {
		printf("\nERR on creating Deque\n");
	}
	return *newDeck;
}
void push_front(int element, Deque* deque) {
	nodeAddr newnode = createNode(element);

	if (is_empty(*deque)) {
		deque->front = newnode;
		deque->back= newnode;
		deque->size++;
		return;
	}
	else {
		newnode->next = deque->front;
		deque->front= newnode;
		deque->size++;
	}

}
void push_back(int element, Deque* deque) {
	nodeAddr newnode = createNode(element);
	if (is_empty(*deque)) {
		deque->front = newnode;
		deque->back = newnode;
		deque->size++;
		return;
	}
	else {
		deque->back->next = newnode;
		deque->back = newnode;
		deque->size++;
		return;
	}
}
int pop_front(Deque* deque) {
	int ret = deque->front->element;
	if (deque->front != NULL) {
		deque->front = deque->front->next;
		deque->size--;
		return ret;
	}
	else
		return -1;

}
int pop_back(Deque* deque) {
	int ret = deque->back->element;
	nodeptr back_prev = deque->front;
	if (back_prev!= NULL) {
		while (back_prev->next != deque->back) {
			back_prev = back_prev->next;
		}
		deque->back = back_prev;
		deque->back->next = NULL;	// free(deque->back->next)
		deque->size--;
		return ret;
	}
	else
		return -1;
}
int size_Deque(Deque deque) {
	return deque.size;
}
int is_empty(Deque deque) {
	if (deque.size == 0)
		return 1;
	else
		return 0;
}
int front(Deque deque) {
	if (!is_empty(deque))
		return deque.front->element;
	else
		return -1;
}
int back(Deque deque) {
	if (!is_empty(deque))
		return deque.back->element;
	else
		return -1;

}

jtw7913 3일 전 1

pop_back의 시간복잡도가 O(n)입니다. while문을 사용하지 않고 마지막 노드를 찾아보는 방법을 생각해보시면 될 것 같습니다

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

문제

문제

출처

ICPC

C에서의 시간초과는 뭘까요?

didqhtmd 3일 전 0

jtw7913 3일 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말