글 읽기 - 채점 3%에서 시간초과... 무엇이 문제일까요?

vhehqhddl1 6년 전 0

계속 코드를 고치고 해봤는데

여전히 채점 3%에서 시간초과가 나옵니다.

뭔가 무한루프가 있는 거 같기도 해서

여러 예시를 돌려보아도 잘 모르겠고...

문제점 좀 찾아주실 수 있나요? ㅠㅠ

#include <stdio.h>
#define MAX 10000

void trans(int, int);
int queue[MAX];
int visit[MAX];
int Array[MAX][2];
int result[MAX];
int i,j,k;
void enq(int value)
{
	queue[i] = value;
	i++;
}
int deq()
{
	int temp = queue[0];
	for(j = 0; j < i; j++)
	{
		queue[j] = queue[j+1];
	}
	queue[i] = 0;
	i--;
	return temp;
}
int main()
{
	//freopen("input.txt","r",stdin);
	int test_case;
	int start, end;
	scanf("%d",&test_case);
	for(int l = 0; l < test_case; l++)
	{
		scanf("%d",&start);
		scanf("%d",&end);
		trans(start, end);
		for(i = 0; result[i] != 0; i++); //거꾸로 출력
		for(j = i-1; j >= 0; j--)
		{
			putchar(result[j]);
			result[j] = 0;
		}
		putchar('\n');
		
		for(i = 0; i < MAX; i++) //초기화
		{
			visit[i] = 0;
		}
		i = 0;
		k = 0;
	}
	return 0;
}
void trans(int start, int end)
{
	int ans = start;
	int D, S, L, R;
	while(1)
	{
		if(ans < 5000)
		{
			D = ans * 2;
		}
		else
		{
			D = ans * 2 % 10000;
		}
		if(ans != 0)
		{
			S = ans - 1;
		}
		else
		{
			S = 9999;
		}
		L = (ans % 1000) * 10 + (ans / 1000);
		R = (ans % 10) * 1000 + (ans / 10);
		
		if(visit[D] == 0){
			enq(D);
			Array[D][0] = 68;
			Array[D][1] = ans;
			visit[D] = 1;
		}
        if(D == end)
		{
			do{
				result[k++] = Array[D][0];
				D = Array[D][1];
			}while(D != start);
			break;	
		}
        
		if(visit[S] == 0){
			enq(S);
			Array[S][0] = 83;
			Array[S][1] = ans;
			visit[S] = 1;
		}
        if(S == end)
		{
			do{
				result[k++] = Array[S][0];
				S = Array[S][1];
			}while(S != start);
			break;	
		}
        
		if(visit[L] == 0){
			enq(L);
			Array[L][0] = 76;
			Array[L][1] = ans;
			visit[L] = 1;
		}
        if(L == end)
		{
			do{
				result[k++] = Array[L][0];
				L = Array[L][1];
			}while(L != start);
			break;	
		}
        
		if(visit[R] == 0){
			enq(R);
			Array[R][0] = 82;
			Array[R][1] = ans;
			visit[R] = 1;
		}
		if(R == end)
		{
			do{
				result[k++] = Array[R][0];
				R = Array[R][1];
			}while(R != start);
			break;	
		}
		ans = deq();
	}
}

mixnuts 6년 전 1

`dequeue` 연산을 $O(N)$으로 짰는데 시간 초과가 안나는게 더 신기한게 아닐까요?

STL라이브러리인 `<deque>`이나 `<queue>`에 대해서 알아보고 사용하신걸 추천드립니다.

vhehqhddl1 6년 전 0

borazone27님 감사합니다!

덕분에 고쳐서 바로 맞췄습니다!

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

문제

문제

출처

ICPC

채점 3%에서 시간초과... 무엇이 문제일까요?

vhehqhddl1 6년 전 0

mixnuts 6년 전 1

vhehqhddl1 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말