글 읽기 - 시간초과가 났습니다 확인좀 해주시면 감사하겠습니다!

tprjs456 3년 전 0

시간초과가 발생했는데 어떤 부분에서 시간초과가 나는지 잘 모르겠습니다!

어떻게 하면 시간초과를 없앨 수 있는지도 조언좀 부탁드리겠습니다!

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

char arr[20001][51];
char arr2[20001][51];

char backup[20001];
int number[20001];

void merge(int a[], int start, int middle, int end) {
	int i = start;
	int j = middle + 1;
	int k = start;

	while (i <= middle && j <= end) {
		if (a[i] <= a[j]) {
			backup[k] = a[i];
			i++;
			k++;
		}
		else {
			backup[k] = a[j];
			j++;
			k++;
		}
	}

	if (i > middle) {
		for (int l = j; l <= end; l++) {
			backup[k] = a[l];
			k++;
		}
	}
	else {
		for (int l = i; l <= middle; l++) {
			backup[k] = a[l];
			k++;
		}
	}

	for (int l = start; l <= end; l++) {
		a[l] = backup[l];
	}
}

void mergesort(int a[], int start, int end) {
	if (start < end) {
		int middle = (start + end) / 2;
		mergesort(a, start, middle);
		mergesort(a, middle + 1, end);
		merge(a, start, middle, end);
	}
}

int main(void) {
	int N;


	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%s", arr[i]);
	}
	//문자열 배열을 각각의 길이의 배열로 변환
	for (int i = 0; i < N; i++) {
		number[i] = strlen(arr[i]);
	}
	//길이를 오름차순으로 정렬
	mergesort(number, 0, N - 1);
	//길이에 맞는 문자열을 다시 arr2에다가 저장
	int k = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (number[i] == strlen(arr[j]) && arr[j][0] != 0) {
				strcpy(arr2[k], arr[j]);
				arr[j][0] = 0;
				k++;
			}
		}
	}
	// 길이마다 사전식으로 정렬
	char temp[51];
	for (int i = 0; i < N; i++) {
		int count = 0;
		for (int j = i + 1; j < N; j++) {
			if (strlen(arr2[i]) == strlen(arr2[j])) {
				count++;
				i = j;
			}
			else {
				break;
			}
		}
		if (count != 0) {
			for (int j = i - count; j <= i; j++) {
				for (int k = j + 1; k <= i; k++) {
					if (strcmp(arr2[j], arr2[k]) == 1) {
						strcpy(temp, arr2[j]);
						strcpy(arr2[j], arr2[k]);
						strcpy(arr2[k], temp);
					}
				}

			}
		}
	}

	printf("\n");
	for (int i = 0; i < N; i++) {
		int j = 0;
		while (arr2[i][j] == arr2[i + 1][j]&&j<=strlen(arr2[i])) {// 같은건 출력하지않도록
			j++;
		}
		if (strlen(arr2[i]) != j - 1) {
			printf("%s\n", arr2[i]);
		}
	}
}

djm03178 3년 전 1

효율적인 정렬을 위해 O(NlogN)의 머지 소트를 사용하셨는데, 71~72번째 줄의 루프는 O(N^2)이고, 94, 95번째 줄도 O(N^2)의 정렬입니다. 이렇게 전체에 대한 이중 반복문을 도는 부분이 없어야 합니다.

tprjs456 3년 전 0

조언 감사드립니다! 다시 풀어보겠습니다!

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

문제

문제

출처

ICPC

시간초과가 났습니다 확인좀 해주시면 감사하겠습니다!

tprjs456 3년 전 0

djm03178 3년 전 1

tprjs456 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말