글 읽기 - 카운팅 정렬 메모리 초과

pha2616 4년 전 0

이 문제 카운팅 정렬로 풀 수 있는 문제 맞나요?

result 배열을 없애고 제출해도 똑같이 메모리 초과가 뜨네요

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int N;
	cin >> N;

	int *arr = new int[N];
	int input, max = 0;
	for (int i = 0; i < N; ++i) {
		cin >> input;
		arr[i] = input;
		if (max < input)max = input;
	}

	int *tmp = new int[max + 1];
	for (int i = 0; i < max + 1; ++i)
		tmp[i] = 0;

	for (int i = 0; i < N; ++i) {
		tmp[arr[i]]++;
	}

	for (int i = 0; i <= max; ++i) {
		while (tmp[i]) {
			cout << i << "\n";
			tmp[i]--;
		}
	}
}

dyk777 4년 전 2

9번 줄과 같이 input의 개수를 미리 파악해서 그 수만큼의 배열을 할당하는 것 자체가 문제입니다.

pha2616 4년 전 0

그래서 다음과 같이 입력을 배열에 안담는 형태로 바꿔봤더니 시간 초과가 나네요ㅜㅜ

#include <iostream>
#include <vector>
using namespace std;

int ans[10000] = { 0, };
int main() {
	int N, input, max = 0;
	cin >> N;

	for (int i = 0; i < N; ++i) {
		cin >> input;
		ans[input]++;
		if (max < input)
			max = input;
	}

	for (int i = 0; i <= max; ++i) {
		while (ans[i]) {
			cout << i << "\n";
			ans[i]--;
		}
	}
}

rhdqor213 4년 전 1

cin, cout은 그냥 쓰면 실행시간이 상당히 느립니다.

이 문제처럼 입력이 1000만개나 되는 문제에선 치명적이죠.

cin, cout을 쓰기 전에 ios::sync_with_stdio(false); 를 써주시면 맞았습니다를 받으실 수 있습니다.

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

문제

문제

출처

ICPC

카운팅 정렬 메모리 초과

pha2616 4년 전 0

dyk777 4년 전 2

pha2616 4년 전 0

rhdqor213 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말