글 읽기 - C++시간초과가 뜹니다,,

kanghun8871 5년 전 0

어제부터 열심히 코드짜서 틀리고 또 짜고 했는데도

마지막엔 시간초과가 나네요,,,

merge sort했는데도 이래요,,ㅠ

도와주시면 감사하겠습니다

#define _CRT_SECURE_NO_WARNINGS

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

void mergeSort(char** arr, int left, int right, int size);
void merge(char** arr, int left, int mid, int right, int size);

int main() {

	int N;
	scanf("%d%*c", &N);

	char** strr = (char**)malloc(sizeof(char*) * N);

	int i;

	for (i = 0;i < N;i++) {
		strr[i] = (char*)malloc(sizeof(char) * 51);
		fgets(strr[i], 51, stdin);
	}

	
	mergeSort(strr, 0, N - 1, N);
	
	for (i = 0;i < N;i++) {
		if ((i<N-1)&&(strcmp(strr[i], strr[i + 1]) == 0))	{free(strr[i]);	continue;}
		printf("%s", strr[i]);
		free(strr[i]);
	}


	free(strr);


	return 0;
}


void mergeSort(char** arr, int left, int right, int size) {
	int mid;

	if (left < right) {
		mid = (left + right) / 2;
		mergeSort(arr, left, mid, size);
		mergeSort(arr, mid + 1, right, size);
		merge(arr, left, mid, right, size);
	}
}

void merge(char** arr, int left, int mid, int right, int size) {

	int i, j, k, m, l, n;

	i = left;
	j = mid + 1;
	k = left;//결과 값의 index

	char** tempArr;

	tempArr = (char**)malloc(sizeof(char*) * size);

	for (n = 0;n < size;n++) {
		tempArr[n] = (char*)malloc(sizeof(char) * 51);
	}

	while ((i <= mid) && (j <= right)) {
		if (strlen(arr[i]) < strlen(arr[j])) {
			strcpy(tempArr[k], arr[i]);
			i++;
		}
		else if (strlen(arr[i]) == strlen(arr[j])) {
			if (strcmp(arr[i], arr[j]) > 0) {
				strcpy(tempArr[k], arr[j]);
				j++;
				}
			else{
				strcpy(tempArr[k], arr[i]);
				i++;
			}
		}
		else {
			strcpy(tempArr[k] ,arr[j]);
			j++;
		}
		k++;
		
	}

	if (i > mid) {
		for (m = j;m <= right;m++) {
			strcpy(tempArr[k], arr[m]);
			k++;
		}
	}
	else {
		for (m = i;m <= mid;m++) {
			strcpy(tempArr[k], arr[m]);
			k++;
		}
	}

	for (m = left;m <= right;m++) {
		strcpy(arr[m],tempArr[m]);
	}

	for (n = 0;n < size;n++) {
		free(tempArr[n]);
	}

	free(tempArr);
}

djm03178 5년 전 0

메모리 할당은 상수 시간이 아니라, 할당하는 크기에 비례합니다. O(size)번의 merge 함수의 호출에 O(size)씩 메모리를 할당하고 해제하니, 총 시간은 O(size^2)가 됩니다.

꼭 필요한 만큼씩만 할당하고 해제하든지, merge를 위한 메모리를 미리 할당해두고 해제 없이 끝까지 사용하세요.

djm03178 5년 전 0

보니까 할당 뿐만 아니라 전체를 옮겼다가 다시 되돌리고 있으니 전체적으로 다 O(size^2)이네요.

kanghun8871 5년 전 0

감사합니다!!

시간초과문제는 해결했는데

이제는 답이 틀렸다고 나오네요,,,ㅠ

제가 생각치 못한 반례가 있나봐요

kanghun8871 5년 전 0

반례가 더 있을까요,,

#define _CRT_SECURE_NO_WARNINGS

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

void mergeSort(char** arr, char** tempArr, int left, int right, int size);
void merge(char** arr, char** tempArr, int left, int mid, int right, int size);


int main() {

	int N;
	scanf("%d%*c", &N);

	char** strr = (char**)malloc(sizeof(char*) * N);

	char** tempArr;

	tempArr = (char**)malloc(sizeof(char*) * N);

	int i;

	for (i = 0;i < N;i++) {
		strr[i] = (char*)malloc(sizeof(char) * 51);
		tempArr[i] = (char*)malloc(sizeof(char) * 51);
		fgets(strr[i], 51, stdin);
	}

	


	
	mergeSort(strr, tempArr, 0, N - 1, N);
	
	for (i = 0;i < N;i++) {
		if ((i<N-1)&&(strcmp(strr[i], strr[i + 1]) == 0))	{free(strr[i]);	free(tempArr[i]); continue;}
		printf("%s", strr[i]);
		free(strr[i]);
		free(tempArr[i]);
	}


	free(tempArr);

	free(strr);

	//getchar();
	return 0;
}


void mergeSort(char** arr, char** tempArr, int left, int right, int size) {
	int mid;

	if (left < right) {
		mid = (left + right) / 2;
		mergeSort(arr, tempArr, left, mid, size);
		mergeSort(arr, tempArr, mid + 1, right, size);
		merge(arr, tempArr, left, mid, right, size);
	}
}

void merge(char** arr, char** tempArr, int left, int mid, int right, int size) {

	int i, j, k, m, l, n;

	i = left;
	j = mid + 1;
	k = left;//결과 값의 index

	

	while ((i <= mid) && (j <= right)) {
		if (strlen(arr[i]) < strlen(arr[j])) {
			strcpy(tempArr[k], arr[i]);
			i++;
		}
		else if (strlen(arr[i]) == strlen(arr[j])) {
			if (strcmp(arr[i], arr[j]) > 0) {
				strcpy(tempArr[k], arr[j]);
				j++;
				}
			else{
				strcpy(tempArr[k], arr[i]);
				i++;
			}
		}
		else {
			strcpy(tempArr[k] ,arr[j]);
			j++;
		}
		k++;
		
	}

	if (i > mid) {
		for (m = j;m <= right;m++) {
			strcpy(tempArr[k], arr[m]);
			k++;
		}
	}
	else {
		for (m = i;m <= mid;m++) {
			strcpy(tempArr[k], arr[m]);
			k++;
		}
	}

	for (m = left;m <= right;m++) {
		strcpy(arr[m],tempArr[m]);
	}


}

djm03178 5년 전 0

51을 모두 52로 바꾸면 맞습니다. 50글자가 한 줄에 들어오면 50 + 개행 문자 + 널 문자까지 총 52칸이 필요합니다.

djm03178 5년 전 0

그래서 이런 문제에서는 개인적으로 fgets는 비추합니다. scanf("%s")가 낫습니다.

kanghun8871 5년 전 0

네 방금 문제 맞았습니다!!

조언 감사합니다!!

행복한 하루되세요

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

문제

문제

출처

ICPC

C++시간초과가 뜹니다,,

kanghun8871 5년 전 0

djm03178 5년 전 0

djm03178 5년 전 0

kanghun8871 5년 전 0

kanghun8871 5년 전 0

djm03178 5년 전 0

djm03178 5년 전 0

kanghun8871 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말