글 읽기 - 어디서 시행 시간을 줄일 수 있을까요?(시간초과)

museum114 5년 전 0

아무래도 알파벳 순으로 정리할 때 시간초과가 되는 것 같은데...

맞나요?? 어떻게하면 좋을까요?

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

typedef struct {
	int m;
	char a[52];
}idea;

void merge(idea *gab, idea *sub_gab, int left, int right, int limit);
int minimum(int a, int b);
void sort(idea *gab, idea *sub_gab, int count);

int main(void)
{
	int input_EA;
	scanf("%d", &input_EA); // Count on input.
	
	idea *pStr = (idea *)malloc(sizeof(idea) * input_EA);
	idea *sub_pStr = (idea *)malloc(sizeof(idea) * input_EA);
	char store[52];

	for (int i = 0; i < input_EA; i++) // store input in pStr
	{
		scanf("%s", pStr[i].a);
		pStr[i].m = strlen(pStr[i].a);
	}

	//find the smallest and put it sub_pStr.
	for (int width = 1; width < input_EA; width *= 2)
	{
		for (int i = 0; i < input_EA; i += 2 * width)
			merge(pStr, sub_pStr, i, minimum(i + width, input_EA), minimum(i + 2 * width, input_EA));
		
		sort(pStr, sub_pStr, input_EA);
	}

	//order in alphabetical order
	
	for (int i = 0; i < input_EA;i++)
	{
		if (pStr[i].m == pStr[i + 1].m) 
		{
			for (int j = i + 1; j < input_EA; j++)
			{
				if (pStr[i].m == pStr[j].m)
				{
					if (strcmp(pStr[i].a, pStr[j].a) > 0)
					{
						strcpy(store, pStr[i].a);
						strcpy(pStr[i].a, pStr[j].a);
						strcpy(pStr[j].a, store);
					}
				}
				else
					break;
			}
		}
	}

	for (int i = 0; i < input_EA; i++)
	{
		if (i != input_EA - 1 && strcmp(pStr[i].a, pStr[i+1].a) == 0) continue;
		
		printf("%s\n", pStr[i].a);
	}
	
	return 0;
}

void merge(idea *gab , idea *sub_gab, int left, int right, int limit)
{
	char temp[50];
	int ileft = left, iright = right;
	for (int k = left; k < limit; k++)
	{
		if ((ileft < right) && (iright >= limit || gab[ileft].m < gab[iright].m))
		{
			sub_gab[k].m = gab[ileft].m;
			strcpy(sub_gab[k].a, gab[ileft++].a);
		}
		else
		{
			sub_gab[k].m = gab[iright].m;
			strcpy(sub_gab[k].a, gab[iright++].a);
		}

	}
	return;
}

int minimum(int a, int b)
{
	return (a > b) ? b : a;
}

void sort(idea *gab, idea *sub_gab, int count)
{
	for (int i = 0; i < count; i++)
		gab[i] = sub_gab[i];

	return;
}

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

문제

문제

출처

ICPC

어디서 시행 시간을 줄일 수 있을까요?(시간초과)

museum114 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말