글 읽기 - 시간초과가 납니다...

jschung 1년 전 0

O(n^2)으로 짜면 안되는건가요...

n<=1000이라 괜찮을 줄 알았는데...

시간초과를 해결할 방법을 알려주실 수 있나요?

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int i,j,k=0,ans=1;
struct str
{
	char a[1001];
};
str s,arr[500501];
bool compare(str x,str y)
{
	if(strcmp(x.a,y.a)<=0)
	{
		return 1;
	}
	return 0;
}
int main()
{
	scanf("%s",s.a);
	for(i=0;i<strlen(s.a);i++)//가능한 모든 문자열 복사
	{
		for(j=0;j<strlen(s.a)-i;j++)
		{
			strncpy(arr[k].a,s.a,j+1);
			k++;
		}
		for(j=0;j<strlen(s.a)-i-1;j++)
		{
			s.a[j]=s.a[j+1];
		}
	}
	sort(arr,arr+k,compare);//복사한 문자열들 정렬
	for(i=1;i<k;i++)//서로 다른 문자열의 개수 계산
	{
		if(strcmp(arr[i].a,arr[i-1].a)!=0)
		{
			ans++;
		}
	}
	printf("%d",ans);
}

jschung 1년 전 0

strlen이 O(n)이라길래 변수에 따로 저장해놓고 다시 해봤는데도 안되네요...

어떻게 해야 하나요

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

문제

문제

출처

ICPC

시간초과가 납니다...

jschung 1년 전 0

jschung 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말