글 읽기 - [C]1181번 단어정렬 시간초과 부탁드립니다...

sangchu8864 3년 전 0

병합정렬을 이용했지만 시간초과가 나왔습니다....

여기서 시간을 어떻게 줄여야할지 모르겠습니다ㅠㅠ

읽어봐주셔서 감사합니다!!

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

char temp_list[20000][52];//array[][0]에는 단어의 길이 나머지는 단어 입력 

void merge(char *list,int left,int mid,int right)
//병합정렬을 위한 합치는 부분 
{
	int i=left,j=mid+1,l=left;
	while(i<=mid&&j<=right)
	{
		if(*(list+52*i)<*(list+52*j))
		{
			strcpy(temp_list[l],list+52*i);
			l++;
			i++;
		}
		else if(*(list+52*i)==*(list+52*j))
		//길이가 같으면 알파벳순으로 비교 
		{
			int n=1;
			while(1)
			{
				if(*(list+52*i+n)<*(list+52*j+n))
				{
					strcpy(temp_list[l],list+52*i);
					l++;
					i++;
					break;
				}
				else if(*(list+52*i+n)>*(list+52*j+n))
				{
					strcpy(temp_list[l],list+52*j);
					l++;
					j++;
					break;
				}
				n++;
				if(n>52)
				break;
			}
		}
				
		else
		{
			strcpy(temp_list[l],list+52*j);
			l++;
			j++;
		}
	}
	
	if(i>mid)
	{
		while(j<=right)
		{
			strcpy(temp_list[l],list+52*j);
			l++;
			j++;
		}

	}
	else
	{
		while(i<=mid)
		{
	        strcpy(temp_list[l],list+52*i);
			l++;
			i++;
		}

	}
	int k=left;
	while(k<=right)
	{
		strcpy(list+k*52,temp_list[k]);
		k++;
	}
}

void merge_sort(char *list,int left,int right)
//병합정렬 함수 
{
	int mid;
	if(left<right)
	{
		mid=left+right;
		mid/=2;
		merge_sort(list,left,mid);
		merge_sort(list,mid+1,right);
		merge(list,left,mid,right);
	}
}
	
		
int main(void)
{
	int n;
	scanf("%d",&n);
	getchar();
	char word[n][52];//word[][0]은 단어의 길이 
	//strcmp("a","a") 같으면 0 출력
	for(int i=0;i<n;i++) //단어입력 
	{
		int j=1;
		while((word[i][j]=getchar())!='\n')
		j++;
		word[i][j]='\0';
		word[i][0]=j-1;//단어의 길이 입력 
	}
	
	merge_sort(word,0,n-1); //병합정렬 
	puts(&temp_list[0][1]); //첫번째 단어 출력
	for(int i=1;i<n;i++) //중복되는 것이 있는지 확인하며 출력 
	{
		int j=1;
		if(strcmp(temp_list[i-1],temp_list[i]))
		{
			puts(&temp_list[i][1]);
		}
	}
	
}
	
				

yijw0930 3년 전 0

병합정렬 자체에 문제가 없다는 가정 하에 50글자의 문자열들을 strcpy로 복붙하면서 정렬하는 대신 문자열의 주소를 저장한 배열을 정렬하면 시간을 아낄 수 있습니다.

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

문제

문제

출처

ICPC

[C]1181번 단어정렬 시간초과 부탁드립니다...

sangchu8864 3년 전 0

yijw0930 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말