글 읽기 - 1181번 C언어 병합정렬 시간초과 질문

kmc724 2년 전 0

안녕하세요 C언어에서 병합정렬을 사용해서 단어를 정렬했습니다.

단어는 잘 정렬이 되는데 시간초과가 계속 출력이 되네요.

어디서 시간이 많이 발생하는지 알 수 있을까요?

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

#define MAX_LENGTH 51

typedef struct
{
	char str[MAX_LENGTH];
	int count;
} string;

void mergesort(string* arr, string* sorted, int left, int right)
{
	int mid;
	int i, j, k;

	if (left >= right)
	{
		return;
	}

	mid = (left + right) / 2;
	mergesort(arr, sorted, left, mid);
	mergesort(arr, sorted, mid + 1, right);

	i = left;
	j = mid + 1;
	k = left;

	for (; k <= right; ++k)
	{
		if (j > right)
		{
			//sorted[k] = arr[i++];
			memcpy(&sorted[k], &arr[i++], sizeof(string));
		}
		else if (i > mid)
		{
			//sorted[k] = arr[j++];
			memcpy(&sorted[k], &arr[j++], sizeof(string));
		}
		else if (strlen(arr[i].str) < strlen(arr[j].str))
		{
			//sorted[k] = arr[i++];
			memcpy(&sorted[k], &arr[i++], sizeof(string));
		}
		else if (strlen(arr[i].str) == strlen(arr[j].str))
		{
			if (strcmp(arr[i].str, arr[j].str) < 0)
			{
				//sorted[k] = arr[i++];
				memcpy(&sorted[k], &arr[i++], sizeof(string));
			}
			else
			{
				//sorted[k] = arr[j++];
				memcpy(&sorted[k], &arr[j++], sizeof(string));
			}
		}
		else
		{
			//sorted[k] = arr[j++];
			memcpy(&sorted[k], &arr[j++], sizeof(string));
		}
	}

	for (i = left; i <= right; ++i)
	{
		//arr[i] = sorted[i];
		memcpy(&arr[i], &sorted[i], sizeof(string));
	}
}

/*
void selection_sort(string* arr, int length)
{
	int min;
	char temp[MAX_LENGTH];

	for (int i = 0; i < length - 1; i++)
	{
		min = i;
		for (int j = i + 1; j < length; j++)
		{
			if (strlen(arr[j].str) < strlen(arr[min].str))
			{
				min = j;
			}
			else if (strlen(arr[j].str) == strlen(arr[min].str))
			{
				if (strcmp(arr[j].str, arr[min].str) < 0)
				{
					min = j;
				}
			}
		}
		if (i != min)
		{
			strcpy(temp, arr[i].str);
			strcpy(arr[i].str, arr[min].str);
			strcpy(arr[min].str, temp);
		}
	}
}
*/
/*
int compare(const void* first, const void* second)
{
	string d1 = *(string*)first;
	string d2 = *(string*)second;

	if (strlen(d1.str) < strlen(d2.str))
	{
		return 0;
	}
	else if (strlen(d1.str) == strlen(d2.str))
	{
		if (strcmp(d1.str, d2.str) < 0)
		{
			return 0;
		}
		else
		{
			return 1;
		}
	}
	else
	{
		return 1;
	}
}
*/
int main(void)
{
	int count;
	string* strarr;
	string* sorted;

	scanf("%d", &count);
	strarr = (string*)malloc(sizeof(string) * count);
	sorted = (string*)malloc(sizeof(string) * count);
	for (int i = 0; i < count; i++)
	{
		scanf("%s", strarr[i].str);
		strarr[i].count = 0;
		for (int j = 0; j < i; j++)
		{
			if (strcmp(strarr[i].str, strarr[j].str) == 0)
			{
				strarr[j].count += 1;
			}
		}
	}
	mergesort(strarr, sorted, 0, count - 1);
	//qsort(strarr, count, sizeof(string), compare);
	for (int i = 0; i < count; i++)
	{
		if (strarr[i].count == 0)
		{
			printf("%s\n", strarr[i].str);
		}
	}

}

kmc724 2년 전 0

정렬되어 있는데 굳이 배열을 다시 탐색할 필요가 없었네요.

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

문제

문제

출처

ICPC

1181번 C언어 병합정렬 시간초과 질문

kmc724 2년 전 0

kmc724 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말