[C++] 백준 10989번 수 정렬하기 3 :: seoftware

문제

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

문제만 읽고 이거 수 정렬하기 2랑 똑같은걸? 이러면서 코드 복붙해서 제출했는데 시간초과 떴다

시간초과 난 코드

#include <iostream>
#include <algorithm>
using namespace std;
int arr[1000000];
int main(void) {
	int N; 
	scanf("%d", &N);
	
	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
	}
	sort(arr, arr + N);
	for (int i = 0; i < N; i++) {
		printf("%d\n", arr[i]);
	}
}

그래서 벡터를 사용해서 다시 제출 해봤는데 메모리 초과가 났다.

메모리초과가 난 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {
	int N; 
	scanf("%d", &N);
	
	vector<int> arr(N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
	}
	sort(arr.begin(), arr.end());
	for (int i = 0; i < N; i++) {
		printf("%d\n", arr[i]);
	}
}

더 줄일 수 없을거같은데 메모리 초과가 나는게 맞나.. 싶어서 조건을 다시 살펴봤다.

N이 10,000,000 일 때 배열을 모두 int 형에 저장하려고 하면 10^7 * 4byte ≒ 10^4 * 4KB ≒ 10 * 4MB 이므로 약 40M이고 이는 메모리제한 8MB를 훨씬 초과한다. 

그럼 방법이 있나.. 하다가 계수정렬(counting sort)이 생각 났다. 

통과한 코드

#include <iostream>
using namespace std;
int arr[10001];
int main(void) {
	int N; 
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int idx;
		scanf("%d", &idx);
		arr[idx]++;
	}
	for (int i = 0; i < 10001; i++) {
		for (int j = 0; j < arr[i]; j++) {
			printf("%d\n", i);
		}
	}
}

 수를 입력받고 해당 인덱스의 값을 ++ 해준다. 출력은 각각의 인덱스에 저장된 횟수만큼 인덱스 i를 출력해주면 된다.

 이렇게 하면 최대 인덱스가 10000이므로 메모리 사용량을 줄일 수 있고, sort 하는 과정도 생략되므로 시간초과도 해결해준다.