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

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

10989번: 수 정렬하기 3

✅ 문제 설명

숫자 N을 입력한 후 N개의 숫자를 입력하면,

N개의 숫자를 오름차순으로 출력하는 문제이다.

---

✅ 알고리즘 설명

 

1. C++ STL sort()

처음에는 간단하게 C++ STL 을 사용하여 정렬을 했다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int n;
    cin >> n;

    vector<int> v;
    while (n--) {
        int a;
        cin >> a;
        v.push_back(a);
    }

    sort(v.begin(), v.end());

    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << '\n';
    }
    return 0;
}

 

그 결과 메모리 초과가 났다.

 

N의 개수가 최대 10,000,000개가 주어질 수 있기 때문에

N의 개수 만큼만 메모리를 할당한다고 쳐도 하나당 4byte씩 총 40,000,000byte = 40MB가 된다.

 

따라서 이 문제의 조건인 8MB를 한참 벗어나는 것이다.

 

2. 배열 사용

 

따라서 위와 같은 방법이 아닌 숫자 배열을 만들어주어 사용했다.

 

 

1) N개의 수는 모두 10,000보다 작거나 같은 자연수라고 했기 때문에 배열을 10,000개 만들어준다.

2) 숫자를 입력할 때 마다 배열에 1씩 더해주어 해당 숫자의 개수를 저장한다.

3) 배열에 저장된 개수만큼 반복해서 같은 수를 출력한다.

---

✅ 코드