글 읽기 - 카운팅정렬 질문입니다.

terry9902 2년 전 0

메모리 초과가 떴는데 최대 입력 갯수가 천만이라 배열 크기를 조정하기도 힘드네요... 어떤 변수를 조정해야 메모리 사용량을 줄일 수 있을까요?

#include<iostream>
//#include<cstdlib>
using namespace std;

void counting(int in[], int sum[], int n);

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//srand(time(NULL));
	int n;
	int* in, * out;
	int* sum;
	int max = -1;
	cin >> n;
	in = new int[n];
	out = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> *(in + i);
		//*(in + i) = rand();
		if (*(in + i) > max)max = *(in + i);
		*(out + i) = -1;
	}
	sum = new int[max + 1];
	for (int i = 0; i <= max; i++)
		sum[i] = 0;
	counting(in, sum, n);
	for (int i = 1; i <= max; i++)
		sum[i] += sum[i - 1];
	for (int i = n - 1; i >= 0; i--) {
		out[sum[in[i]] - 1] = in[i];
		sum[in[i]]--;
	}
	for (int i = 0; i < n; i++)
		cout << out[i] << '\n';
	delete[] in;
	delete[] out;
	delete[] sum;
	return 0;
}

void counting(int in[], int sum[], int n) {
	for (int i = 0; i < n; i++)
		sum[in[i]]++;
}

0000000000 2년 전 1

입력값을 굳이 배열에 저장할 필요가 있을까요?

terry9902 2년 전 0

배열을 누적합 저장하는 것만 사용해도 계산이 가능하네요

고정관념을 깨주셔서 감사합니다

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

문제

문제

출처

ICPC

카운팅정렬 질문입니다.

terry9902 2년 전 0

0000000000 2년 전 1

terry9902 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말