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

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

10989번: 수 정렬하기 3

 

문제분석

N개의 수가 주어지고, 이를 오름차순으로 정렬하는 문제이다.

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

출력으로는 둘째 줄부터의 입력들을 오름차순으로 정렬하면 된다.

예를 들어, 첫째 줄에 5가 주어지고 두번째 줄부터 차례로 3 6 9 3 6 이 주어졌다고 했을 때,

출력으로 3 3 6 6 9를 만들면 된다.

그러나 이 문제는 시간제한 및 메모리 제한이 존재한다.

즉, 입력받은 수를 다 저장하고 다시 정렬하고자 하면 8MB의 메모리를 초과해버린다.

-> 4byte의 수가 총 10^7개 만큼 올 수 있으니 이는 4*10^7byte로 40MB이기 때문

​

코드

#include<iostream>
using namespace std;

int num;
int arr[10001]; // 배열의 인덱스는 1부터 시작하므로 최대값보다 +1

int main(){
    ios_base::sync_with_stdio(false)
	cin.tie(NULL);
	cout.tie(NULL);

	int temp;
	cin >> num;

	for (int i = 0; i < num; i++) {
		cin >> temp;
		arr[temp]++;    // 입력으로 들어온 숫자에 해당하는 인덱스의 값 ++
	}
	for (int i = 1; i < 10001; i++) {
		for (int j = 0; j < arr[i]; j++) {
			printf("%d\n", i);  // 그냥 출력하지 않고 for문을 한번 더 사용하는 이유
                                //  => 입력으로 들어온 것 중 동일한 수가 있을 수 있기 때문
		}
	}
	return 0;
}

 

문제풀이

1. 시간복잡도 해결

위 코드의 이중 for문은 O(N^2)의 시간복잡도를 가지게 되고, 그로 인해 문제가 요구하는 시간을 초과해버리는 문제가 발생한다.

위 코드는 c와 c++의 표준 stream의 동기화를 끊어주는 역할을 한다.

따라서 cin과 cout의 속도가 빨라져 시간초과 문제를 해결할 수 있다.

또는, cin과 cout 대신 scanf와 printf를 사용한다면 위 코드 없이도 해결 가능하다.

endl 대신 \n을 써주는 것도 좋다.

​

2. 공간복잡도 해결

앞서 말했듯, 메모리제한으로 인해 sort()함수를 사용할 수 없다.

정렬해야 하는 수의 범위가 1 이상 10,000 이하이므로 계수정렬(Counting sort)을 이용한다.

​

계수정렬이란? 원소들간 비교 없이 정렬을 할 수 있는 알고리즘이다.

(음수, 소수에는 불가능)

(수의 범위가 상대적으로 작은 경우에 유용한 정렬)

​

크기가 10,000인 배열을 하나 생성 후, 각 원소가 몇번 등장하는지 세어준다.

그리고 배열을 처음부터 끝까지 방문하면서 해당 숫자를 등장한 횟수만큼 출력하면 끝!!

---

참조

https://m.blog.naver.com/jryoun1/222094707603

계수 정렬 (Counting Sort)