Sorting(Memory관련)

문제설명

문제

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

입력

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

출력

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

접근

이 문제는 메모리 제한이 8MB인 문제이다. 일반적인 Sorting 알고리즘을 사용하면 숫자를 저장하기위한 배열의 메모리공간으로만 이미 메모리초과가 난다.(10⁷ * 2bytes > 8MB)

이 문제는 1~10000사이의 수만 들어오므로 길이가 10000인 배열을 가지고 숫자를 count하면 된다. count가 끝난 후 오름차순으로 count한 갯수만큼 출력하면 메모리초과없이 해결할 수 있다.

코드

#include <iostream>
#define MAX_NUM 10000
using namespace std;

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

    int n, tmp;
    cin >> n;
    int arr[MAX_NUM];
    fill(arr, arr+MAX_NUM, 0);
    for(int i=0; i<n; i++){
        cin >> tmp;
        arr[tmp-1]++;
    }

    for(int i=0; i<MAX_NUM; i++){
        for(int j=arr[i]; j>0; j--)
            cout << i+1 << '\n';
    }
}

참고

BOJ #10989

이 글이 도움이 되셨다면 추천 클릭을 부탁드립니다 :)