10989_수 정렬하기3

10989_수정렬하기3

최대 10,000,000개의 수가 주어질 수 있으므로 vector, 동적할당 등을 사용하면 무조건 메모리초과 오류가 발생한다. 그래서 조건에 '이 수는 10,000보다 작거나 같은 자연수이다.' 에 초점을 맞추어 본다.

array[index]	Value
array[1]	0
array[2]	1
array[3]	2
array[4]	0
array[5]	4
array[6]	0

위와 같이 입력으로 주어지는 수를 index로하는 배열의 value값을 하나씩 올려주면서 값을 저장한다. 그리고 출력하는 부분은 다음과 같이 코드를 작성한다.

 for(int i=1;i<10001;i++){
        if(arr[i] != 0) {
            for(int j=0;j<arr[i];j++){
                printf("%d\n",i);
            }
        }
    }

arr[i]가 0이 아니면 그 value의 값 만큼 index를 출력해주는 것이다. 이는 문제에서 원한 조건과 일치한다. 위 방법은 배열의 크기가 충분하지 않는 정렬 문제에서 해결할 수 있는 방법이다.

전체코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
​
​
#define IOFAST() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int arr[10001];
​
int main() {
    IOFAST();
    int T;
    cin >> T;
​
    while(T--) {
        int value;
        cin >> value;
        arr[value]++;
    }
​
    for(int i=1;i<10001;i++){
        if(arr[i] != 0) {
            for(int j=0;j<arr[i];j++){
                printf("%d\n",i);
            }
        }
    }
​
}