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

문제

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

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

---

 

브론즈 1티어.

처음에는 아무 생각 없이 배열에다가 입력을 모두 저장하고, 버블 정렬 식으로 풀면 된다고 생각했는데

특이하게도 이 문제는 메모리 제한이 8MB이었다.(아주 작은 편)

그래서 배열 크기 + 정렬 시간 -> 실패 예감

// 아래는 메모리 초과 코드
int main() {
	int n;
	int a = 0;
	int nums[10000000] = { 0, };
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> nums[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			if (nums[i] > nums[j]) {
				a = nums[i];
				nums[i] = nums[j];
				nums[j] = a;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		cout << nums[i] << "\n";
	}
}

 

그래서 10000개짜리 배열을 만들고 입력받은 곳의 인덱스만 count하여 그 갯수만큼 인덱스를 출력하는 방식으로

문제를 해결해야 한다.

그리고 처음에 쓸데없이 if문 넣었다가 시간 초과가 떠서

if문은 지우고, cin/cout 입출력 시간 줄이는 코드까지 넣어서 마침내 성공했다.

 

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	int a = 0;
	int nums[10000] = { 0, };
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a;
		nums[a-1] += 1;
	}
	for (int i = 0; i < 10000; i++) {
		for (int j = 0; j < nums[i]; j++) {
			cout << i + 1 << "\n";
		}
	}
}