글 읽기 - c언어 시간초과 해결 할 수 있는 방법이 있나요?? 1874

yunafrica 3년 전 0

결과는 알맞게 나오는 것 같은데, 자꾸 시간초과가 나네요..

int flag가 0이 되면 빠져나오도록 if(break)를 걸어주면, input값이 다 입력되기전에 중간에 NO값이 출력되서 빠져나오므로 틀리는 것 같습니다.

(아닐수도 있지만, 잘 모르겠습니다..)

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

void print_all(char *stack,int a)
{
	int i = 0;
	// int count = 100;
	while (stack[i] && i < a)
	{
		printf("%c\n",stack[i]);
		i++;
	}
	// for (size_t i = 0; i < count; i++)
	// {
	// 	printf("%c\n",stack[i]);
	// }
	
	return ;
}

void print_input(char *stack, char c)
{
	int i = 0;
	while (stack[i])
	{
		i++;
	}
	stack[i] = c;
	return ;
}

void zero_forward(int *stack, int *temp)
{
	int i = *temp;
	while (stack[i] == 0 && i > 0)
	{
		i++;
	}
	*temp = i;
}

void zero_backward(int *stack, int *temp)
{
	int i = *temp;
	while (stack[i] == 0 && i > 0) //에러나지 말라고 해줬네
	{
		i--;
	}
	*temp = i;
}


int main()
{
	int count;
	int input;
	int flag = 1;
	int temp = 0;
	int a=0;
	scanf("%d",&count);
	int n = 0;
	char *print_c;
	// unsigned int stack[count];
	int *stack;
	stack = malloc(sizeof(int) * (count + 1));
	print_c = malloc(sizeof(char) * (2 * count));
	memset(print_c, 0, 2*count);
	for (size_t i = 0; i < count + 1; i++)
	{
		stack[i] = i;
	}
	// print_all(print_c);
	while (n < count)
	{
		if (flag == 0)
		// 	break;
		scanf("%d", &input);
		if (temp < input)
		{
			while(temp != input)
			{
				a++;
				temp++;
				zero_forward(stack, &temp);
				print_input(print_c,'+');
				// printf("+\n");
			}
			a++;
			stack[temp] = 0;
			print_input(print_c,'-');
			// printf("-\n");
		}
		else if (temp >= input)
		{
			temp--;
			zero_backward(stack, &temp);
			if (temp != input && n != count -1)
			{
				flag = 0;
				// break;
			}
			a++;
			stack[temp] = 0;
			print_input(print_c,'-');
			// printf("-\n");
		}
		n++;
	}
	if (flag == 0)
		printf("NO\n");
	else
	{
		print_all(print_c,a);
	}
	free(stack);
	free(print_c);
	return 0;
}

yunafrica 3년 전 0

break문으로 빠져나와도 됩니다.

문제가 되었던 부분은 반복문을 통해 탐색하면, 문제가 발생합니다.

따라서, 배열이 어디까지 씌였는지 탐색하지않아도 되도록 배열의 index의 위치를 저장하는 `unsigned int i` 선언하여 위치를 파악하도록

코드를 수정하였습니다.

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

문제

문제

출처

ICPC

c언어 시간초과 해결 할 수 있는 방법이 있나요?? 1874

yunafrica 3년 전 0

yunafrica 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말