글 읽기 - 시간 초과로 돌겠습니다...

surung9898 5년 전 0

와.. 처음에 Postorder을

void poo(link ptr)

{

poo(str->lr);

poo(str->rr);

printf("%d\n", ptr->num);

}

이렇게 재귀로 부르니 시간초과가 떠서 이번엔 재귀를 쓰지 않고 해봤는데도 터지네요...

시간 줄일 수 있는 방법 좀 전수해주십시오 굇수님들니뮤ㅠㅠㅠ

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

typedef struct node* link;
typedef struct node
{
	int num;
	link lr;
	link rr;
	int visit;
} node;

link createN(link head, int num)
{
	link temp, c = NULL, trail = NULL;
	int lr = 0;

	temp = (link)malloc(sizeof(node));
	temp->num = num;
	temp->lr = NULL;
	temp->rr = NULL;
	temp->visit = 0;

	if (!head)
	{
		head = temp;
		return head;
	}

	c = head;

	while (c)
	{
		if (c->num > num)
		{
			trail = c;
			c = c->lr;
			lr = 0;
		}
		else
		{
			trail = c;
			c = c->rr;
			lr = 1;
		}
	}

	if (lr == 0) trail->lr = temp;
	else trail->rr = temp;

	return head;
}
void poo(link ptr)
{
	link st[10001];
	int stcnt = 0, i = 0;

	st[0] = ptr;

	while (stcnt != -1)
	{
		if (ptr->rr && !ptr->rr->visit)
		{
			stcnt++;
			st[stcnt] = ptr->rr;		
		}

		if (ptr->lr && !ptr->lr->visit)
		{
			stcnt++;
			st[stcnt] = ptr->lr;		
		}

		if ((!ptr->lr || ptr->lr->visit) && (!ptr->rr || ptr->rr->visit))
		{
			printf("%d\n", ptr->num);
			ptr->visit = 1;
			st[stcnt] = NULL;
			stcnt--;
		}

		ptr = st[stcnt];
	}
}

int main()
{
	link head = NULL;
	int i, temp, cnt = 0;

	while (1)
	{
		scanf("%d", &temp);

		if (!temp) break;

		else head = createN(head, temp);
	}

	poo(head);

	return 0;
}

portableangel 5년 전 1

입력이 0으로 끝난다는 이야기가 없습니다.

입력이 주어지는 동안 계속 입력을 받으시려면 아래와 같이 하시면 됩니다.

while (scanf("%d", &temp) == 1) { //scanf는 입력받는 데에 성공한 인자의 개수를 리턴합니다.
    //todo
}

surung9898 5년 전 0

와 진짜 감사합니다 ㅠㅠ 진짜 신기하네요 이거 바꿨다고 시간이 이렇게 단축되다니

portableangel 5년 전 2

단축이 아니라, 이전 코드는 가능한 모든 입력에서 무한루프로 시간초과입니다. 존재하지 않는 입력을 영원히 기다리고 있으니까요.

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

문제

문제

출처

ICPC

시간 초과로 돌겠습니다...

surung9898 5년 전 0

portableangel 5년 전 1

surung9898 5년 전 0

portableangel 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말