글 읽기 - C 버퍼 관련한 시간초과 질문 드립니다.

rkdgus 5년 전 0

덱을 통해서 문제를 해결하였습니다.

기존에 시간초과가 나서 왜 그런가 찾아보았더니 버퍼쪽 문제인걸 알고, 버퍼를 이런저런 방법으로 비워보다가 해결하게 되었습니다.

제가 궁금한건 28번째 줄부터 시작되는 main() 내에서 44, 51번째 줄의 버퍼 비우는 코드를 getchar()로 대체하게 되면 왜 시간초과가 나는지 입니다. getchar()로 대체하게 될 경우 예제와 제가 무작위로 입력해본 케이스들이 모두 정상적으로 출력되었으나, 문제를 제출하면 25%쯤에서 멈춘 뒤 시간초과가 일어나더라고요.

일단 추측컨데 이러한 시간초과가 main() 내부, 특히 getchar() 부분의 문제라 생각해서 질문 올립니다.

// 덱 deque(double ended queue)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct DoublyListNode {
	int data;
	struct DoublyListNode *leftLink;
	struct DoublyListNode *rightLink;
}DoublyListNode;

typedef struct DequeType {
	DoublyListNode *head;
	DoublyListNode *tail;
}DequeType;

DoublyListNode *createNode(DoublyListNode *leftLink, int item, DoublyListNode *rightLink);
void addLear(DequeType *dq, int item);
void addFront(DequeType *dq, int item);
void deleteLear(DequeType *dq);
void deleteFront(DequeType *dq);
void deleteAll(DequeType *dq);
bool checkEmpty(DequeType *dq);
void init(DequeType *dq);
void printHeadToTail(DequeType *dq);
void printTailToHead(DequeType *dq);

int main() {	
	int tc, funcSize, temp;
	int seqSize, seqValue = 0;
	bool isError = false;
	bool isDirectionalLeft;
	char funcArr[100001] = "";
	
	scanf("%d", &tc);
	while (tc--) {
		DequeType deque;
		init(&deque);
		isDirectionalLeft = false;
		isError = false;
        
		scanf("%s", funcArr);
		scanf("%d", &seqSize);
		while ((temp = getchar()) != EOF && temp != '\n');    // buffer clear
        // getchar()

		while (seqSize--) {
			scanf("%*c%d", &seqValue);
			addLear(&deque, seqValue);
		}
		while ((temp = getchar()) != EOF && temp != '\n');    // buffer clear
		// getchar()

		funcSize = strlen(funcArr);
		for (int i = 0; i < funcSize; i++) {
			switch (funcArr[i]) {
			case 'R':
				isDirectionalLeft = !isDirectionalLeft;
				break;
			case 'D':
				if (checkEmpty(&deque)) {
					isError = true;
					break;
				}
				if (isDirectionalLeft)
					deleteLear(&deque);
				else
					deleteFront(&deque);
				break;
			}
		}
		if (isError)
			printf("error\n");
		else if (isDirectionalLeft)	// true일 경우 tail -> head 순으로 출력
			printTailToHead(&deque);
		else
			printHeadToTail(&deque);

		deleteAll(&deque);	// 메모리 관리, 시간에 영향 거의 없음
	}
	return 0;
}

DoublyListNode* createNode(DoublyListNode *leftLink, int item, DoublyListNode *rightLink) {
	DoublyListNode *node = (DoublyListNode *)malloc(sizeof(DoublyListNode));
	if (node == NULL) exit(1);
	node->leftLink = leftLink;
	node->data = item;
	node->rightLink = rightLink;
	return node;
}
void addLear(DequeType *dq, int item) {
	DoublyListNode *newNode = createNode(dq->tail, item, NULL);
	if (checkEmpty(dq))
		dq->head = newNode;
	else
		dq->tail->rightLink = newNode;
	dq->tail = newNode;
}
void addFront(DequeType *dq, int item) {
	DoublyListNode *newNode = createNode(NULL, item, dq->head);
	if (checkEmpty(dq))
		dq->tail = newNode;
	else
		dq->head->leftLink = newNode;
	dq->head = newNode;
}
void deleteFront(DequeType *dq) {
	DoublyListNode *removedNode;
	//if (checkEmpty(dq)) exit(1);	// checkEmpty()는 main에서 사용
	removedNode = dq->head;
	dq->head = dq->head->rightLink;
	free(removedNode);
	if (dq->head == NULL)
		dq->tail = NULL;
	else
		dq->head->leftLink = NULL;
}
void deleteLear(DequeType *dq) {
	DoublyListNode *removedNode;
	//if (checkEmpty(dq))exit(1);	// checkEmpty()는 main에서 사용
	removedNode = dq->tail;
	dq->tail = dq->tail->leftLink;
	free(removedNode);
	if (dq->tail == NULL)
		dq->head = NULL;
	else
		dq->tail->rightLink = NULL;
}
void deleteAll(DequeType *dq) {
	while (!checkEmpty(dq))
		deleteFront(dq);
}
bool checkEmpty(DequeType *dq) {
	return (dq->head == NULL) ? true : false;
}
void init(DequeType *dq) {
	dq->head = dq->tail = NULL;
}
void printHeadToTail(DequeType *dq) {
	DoublyListNode *p;
	printf("[");
	if (dq->head != NULL) {
		for (p = dq->head; p->rightLink != NULL; p = p->rightLink)
			printf("%d,", p->data);
		printf("%d]\n", p->data);
	}
	else
		printf("]\n");
}
void printTailToHead(DequeType *dq) {
	DoublyListNode *p;
	printf("[");
	if (dq->tail != NULL) {
		for (p = dq->tail; p->leftLink != NULL; p = p->leftLink)
			printf("%d,", p->data);
		printf("%d]\n", p->data);
	}
	else
		printf("]\n");
}

djm03178 5년 전 1

처음에 배열이 비어있으면 52번째 줄의 getchar는 '['를 읽고 ']'가 버퍼에 남습니다. 그래서 다음 테스트 케이스에서 문제가 생깁니다.

2
R
0
[]
R
1
[1]

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

문제

문제

출처

ICPC

C 버퍼 관련한 시간초과 질문 드립니다.

rkdgus 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말