[백준] 10989번: 수 정렬하기 3 C++로 풀어보기

10989번 설명

생각

수의 개수가 천만개까지 주어진다. 일반적인 방법을 썼다가는 분명히 시간이든 메모리든 초과가 뜰 것 같다.

 

그래서 그냥 sort는 안될 것 같고, merge sort를 써보기로 하였다.

-> merge sort를 사용해도 메모리 초과가 되었다. 

 

그래서 그냥 sort를 써보았다.

-> 당연히 안됐다.

 

왜 자꾸 메모리 초과가 뜰까? 배열을 천만개를 선언해서 그런가? 그러면 벡터를 써볼까?

-> 그래도 안됐다.

 

그렇다면 주어진 수는 10000보다 작으니, 주어진 수를 10000 크기의 배열에 넣고 그 배열을 순회하면서 배열에 들어간 수만큼 그 숫자를 출력한다.

-> 몇번의 실패끝에, 드디어 성공했다.

 

코드

#include <bits/stdc++.h>
typedef long long ll; // 큰 수가 쓰이므로 int 대신 long long을 쓰기로 했다. long long을 ll로 쓸 수 있다.
using namespace std;
ll arr[10005];


int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin >> n;
    for (ll i = 0; i < n; i++) { // 만약 5가 입력되면, arr[5]에 숫자가 1 증가된다
        ll x;
        cin >> x;
        arr[x] = arr[x] + 1; 
    }

    for (ll i = 1; i <= 10000; i++) {
        if (arr[i] != 0) { // 0이 아니라면
            for (ll j = 0; j < arr[i]; j++) {
                cout << i << "\n"; // arr[i]에 들어간 숫자만큼 i가 출력된다
            }
        }
    }
}

 

결과

10989번 결과

왜 정답률이 23%인지 알 수 있었다. 앞으로 메모리 관리에도 유의할 것!