수 정렬하기 3

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
5 초	8 MB	209707	48717	36866	23.513%

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다.

둘째 줄부터 N개의 줄에는 수가 주어진다.

이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

10
5
2
3
1
4
2
3
5
1
7

예제 출력 1

1
1
2
2
3
3
4
5
5
7

출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: cgiosy
• 문제의 오타를 찾은 사람: joonas

비슷한 문제

• 2750번. 수 정렬하기
• 2751번. 수 정렬하기 2

알고리즘 분류

• 정렬

---

메모리 초과

아무 생각 없이 N의 최대값만큼 배열을 선언하고 정렬하여 출력하려고 했다.

제출하고 보니 메모리 초과….응?

문제를 확인해보니 메모리 제한이 8MB이다…!

#include <iostream>
#include <algorithm>

using namespace std;

int arr[10000001];

int N;

int main()
{
	cin >> N;
	int temp = 0;
	while (temp < N ) {
		cin >> arr[temp];
		temp++;
	}

	sort(arr, arr + N);

	for (int i = 0; i < N; i++) {
		cout << arr[i] << "\n";
	}

	return 0;
}

시간 초과

메모리가 너무 적으니 다른 방법을 생각했다.

주어지는 수는 최대값이 10,000보다 작은 자연수

해당 크기만큼 배열을 선언하고 배열의 인덱스 수가 나오면 해당 배열의 값을 1 추가하는 방법이다.

만약 i 가 나온다면 arr[i]++ <= 카운트하고 값만큼 그 인덱스를 출력해주는 방법

#include <iostream>

using namespace std;

int arr[10001];

int N, temp;

int main()
{
	cin >> N;
	while (N-- > 0) {
		cin >> temp;
		arr[temp]++;
	}

	for (int i = 1; i <= 10000; i++) {
		for (int j = 0; j < arr[i]; j++) {
			cout << i << "\n";
		}
	}

	return 0;
}

아무리 생각해도 이것보다 빠를 순 없을 텐데… 시간 초과…

이것저것 시험해 보다가 해결이 안 돼서 다른 글들을 찾아보았다.

결과적으로 입력과 출력의 문제였다. cin / cout

https://stackoverflow.com/questions/31162367/significance-of-ios-basesync-with-stdiofalse-cin-tienull <- 원글

https://jaimemin.tistory.com/1521 <- 퍼온곳

통과된 코드

ios_base::sync_with_stdio(false); 로 동기화를 풀어주자

#include <iostream>

using namespace std;

int arr[10001];

int N, temp;

int main()
{

	ios_base::sync_with_stdio(false); // 동기화를 비활성화
	// cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	while (N-- > 0) {
		cin >> temp;
		arr[temp]++;
	}

	for (int i = 1; i <= 10000; i++) {
		if (arr[i] == 0) continue;

		for (int j = 0; j < arr[i]; j++) {
			cout << i << "\n";
		}
	}

	return 0;
}

아 빡쳐