글 읽기 - 50퍼센트에서 시간초과 나오네여 ㅠ

riamoney92 6년 전 0

링크드 리스트 구현해서 사용했구여 테스트 케이스마다 모든 노드를 free하면 시간걸려서 그냥 head만 free 해줘도 시간 초과에 걸리네여 ㅠㅠ

코드에서 최적화 부분 도움 좀 주시면 감사합니다. ㅠㅠ

#include <cstdio>
#include <cstdlib>
#include <cstring>

typedef struct Node{
	Node *prev, *next;
	char data;
}Node;

// variable
Node *head, *current;
int t;

// functions
int isTail() {
	if(current->next == NULL) return 1;
	return 0;
}

void init() {
	if(head != NULL) free(head);

	head = (Node*)malloc(sizeof(Node));

	head->prev = NULL;
	head->next = NULL;
	head->data = NULL;

	current = head;
}

void insert(char data) {
	if(isTail()) {
		Node *newNode = (Node*)malloc(sizeof(Node));
		newNode->data = data;
		newNode->prev = current;
		newNode->next = NULL;

		current->next = newNode;

		current = newNode;
	} else {
		Node *newNode = (Node*)malloc(sizeof(Node));
		newNode->data = data;
		newNode->prev = current;
		newNode->next = current->next;

		current->next->prev = newNode;
		current->next = newNode;

		current = newNode;
	}
}

void remove() {
	if(current == head) return;

	if(isTail()) {
		Node *deleteNode = current;
		current->prev->next = NULL;
		current = current->prev;

		free(deleteNode);
	} else {
		Node *deleteNode = current;
		current->prev->next = current->next;
		current->next->prev = current->prev;
		current = current->prev;

		free(deleteNode);
	}
}

int main() {
// input
	scanf("%d", &t);

	while(t--) {
		char str[1000001];
		scanf("%s", str);
		
// init
		init();

// algorithm	
		for(int i=0; i<strlen(str); i++) {
			char currentCh = str[i];

			switch(currentCh) {
			case '-' :
				remove();
				break;
			case '<' :
				if(current != head) current = current->prev;
				break;
			case '>' :
				if(!isTail()) current = current->next;
				break;
			default :
				insert(currentCh);
				break;
			}
		}

// result
		current = head->next;
		while(1) {
			printf("%c", current->data);
			if(isTail()) break;
			current = current->next;
		}
		printf("\n");
	}
	
	return 0;
}

sgchoi5 6년 전 2

시간 초과가 코드 구현 상의 문제라면.. (특정 상황에서 무한 루프)

대회에서 사용했던 TC 를 한 번 이용해보시고요.. http://gooddaytocode.blogspot....

정답코드는 아마.. 스택 2 개를 이용해서 간단히 처리했던 것 같네요..

riamoney92 6년 전 0

답변 감사합니다. TC 돌려보니까 단순 시간 초과네요. 다르게 접근해야 겠네여.

ljh9032a 6년 전 0

sgchoi5님 스텍 2개로 처리했다하셧는데 어떻게 구상하셧는지 궁금하네요~

알려주실수 있으신가요!!

sgchoi5 6년 전 0

@ljh9032a 님, 출제자 설명인지 답안코드인지 정확히 기억은 안나는데..

stack 2 개를 이용해서 커서의 왼쪽, 오른쪽 데이터를 만들어 두고

커서 이동에 따라서 데이터를 이동 시키고요.. 마지막에 커서의 오른쪽에 모두 모은 후 꺼내서 출력하는 방식입니다.

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

문제

문제

출처

ICPC

50퍼센트에서 시간초과 나오네여 ㅠ

riamoney92 6년 전 0

sgchoi5 6년 전 2

riamoney92 6년 전 0

ljh9032a 6년 전 0

sgchoi5 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말