글 읽기 - 메모리 초과 도저히 해결이 안됩니다 부탁드립니다

skatjdehddms 2년 전 0

병합정렬을 이용했고 중복제거는 이중 for문을 이용해서 입력할때 미리 제거를 했습니다 예제는 잘 나오고 여러가지 질문에 있던 예시들도 잘 나옵니다 그런데 자꾸 제출을 하면 초반에 메모리 초과가 납니다 혹시나 무한반복이 문제인가 싶어 제가 아는 선에서는 무한 반복이 생기지 않게 수정했는데도 안됩니다 2일째 골머리를 앓고있습니다 제발 부탁드립니다

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
using namespace std;

class word
{
private:
	char* a;
public:
	word()
	{

	}
	void init(char* arr)
	{
		a = new char[strlen(arr)];
		strcpy(a, arr);
	}
	int getlen()
	{
		return strlen(a);
	}
	char gets(int i)
	{
		return a[i];
	}
	int check(char* arr)
	{
		if (strcmp(a, arr))
			return 1;
		else
			return 0;
	}
	void print()
	{
		cout << a << "\n";
	}
};
void sort(word arr[], int left, int right, word t[])
{
	int L = left;
	int mid = (left + right) / 2;
	int R = mid + 1;
	int k = left;
	while (L <= mid && R <= right)
	{
		//t[k++] = arr[L] <= arr[R] ? arr[L++] : arr[R++];
		if (arr[L].getlen() < arr[R].getlen())
			t[k++] = arr[L++];
		else if (arr[L].getlen() > arr[R].getlen())
			t[k++] = arr[R++];
		else
		{
			int i = 0;
			while (i < 52)
			{
				if (arr[L].gets(i) < arr[R].gets(i))
				{
					t[k++] = arr[L++];
					break;
				}
				else if (arr[L].gets(i) > arr[R].gets(i))
				{
					t[k++] = arr[R++];
					break;
				}
				else
					i++;
			}
		}

	}
	if (L > mid)
	{
		for (int i = R; i <= right; i++)
			t[k++] = arr[i];
	}
	else
	{
		for (int i = L; i <= mid; i++)
			t[k++] = arr[i];
	}
	for (int i = left; i <= right; i++)
	{
		arr[i] = t[i];
	}
}
void separate(word arr[], int left, int right, word t[])
{
	if (left == right)
	{
		return;
	}
	int mid;
	mid = (left + right) / 2;
	separate(arr, left, mid, t);
	separate(arr, mid + 1, right, t);
	sort(arr, left, right, t);
}

int main()
{
	int a;
	cin >> a;
	word* arr = new word[a];
	word* t = new word[a];
	char r[51];
	cin >> r;
	arr[0].init(r);
	for (int i = 1; i < a; i++)
	{
		char s[51];
		cin >> s;
		for (int j = 0; j < i; j++)
		{
			if (arr[j].check(s))
			{
				arr[i].init(s);
			}
			else
			{
				i--;
				a--;
			}
		}
	}
	separate(arr, 0, a - 1, t);
	for (int i = 0; i < a; i++)
	{
		arr[i].print();
	}
	return 0;
}

djm03178 2년 전 0

중복 체크의 로직이 잘못되었습니다.

현재 코드는 새로운 문자열이 입력되면 이전까지 문자열들 중 중복이 아닌 것이 나올 때마다 init을 하게 됩니다. 물론 결과적으로는 하나만 저장이 되겠지만, init에서 호출하는 new로 할당된 메모리 자체는 계속해서 누적되게 됩니다. 중복되지 않는 경우 init을 한 번만 수행하도록 해야 합니다.

또한 new를 할 때 할당되어야 하는 메모리는 strlen(arr)보다 1 이상 더 커야 합니다. 널 문자가 들어갈 자리가 필요하기 때문입니다.

dustkd1004 2년 전 0

중복제거를 정렬 후에 해보시는 건 어떠신가요?

정렬 알고리즘이 올바르면 중복된 원소들은 붙어있기 때문에 쉽게 제거 가능합니다.

그리고 STL은 의도적으로 안쓰시는 건가요?

C++ 쓰시는 거면 sort는 STL 사용하는 걸 추천드립니다.

djm03178 2년 전 0

또한 이 코드는 중복 체크의 로직이 다소 비효율적이라, 아마도 데이터 추가를 통해 저격이 가능할 것으로 보입니다.

skatjdehddms 2년 전 0

문제였던 메모리 초과는 해결됐는데 이제는 시간초과가 걸리네요 기존보단 많이 진행이 된걸 보니 개선은 된거같은데 아직도 기준에 못 미치나 봅니다 여기서 어떻게 더 시간을 줄여야할지 모르겠습니다.

skatjdehddms 2년 전 0

클래스를 통해서 모든걸 해보려 해봤는데 불필요한 움직임이 너무 많은거같아서 걍 다 지워버리고 string로 해봤는데 그게 정답이었습니다 바보같은 고집을 속죄하는 마음 뿐입니다

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

문제

문제

출처

ICPC

메모리 초과 도저히 해결이 안됩니다 부탁드립니다

skatjdehddms 2년 전 0

djm03178 2년 전 0

dustkd1004 2년 전 0

djm03178 2년 전 0

skatjdehddms 2년 전 0

skatjdehddms 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말