[BOJ 10989 / C++] 수 정렬하기 3 (정렬)

문제링크: https://www.acmicpc.net/problem/10989

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    int n;
    cin >> n;
    
    int num;
    int arr[10001];
    fill(arr, arr+10001, 0);

    for (int i = 0; i < n; i++) {
        cin >> num;
        arr[num]++;
    }
    
    for (int i = 1; i <= 10000; i++) {
        while (arr[i]) {
            cout << i << '\n';
            arr[i]--;
        }
    }
}

 

 

2. 시간복잡도

그냥 vector를 사용해서 sort로 끝내면 메모리 초과가 발생한다. 메모리 제한이 8MB로 굉장히 짠 것을 알 수 있다. 수의 갯수가 10^7이고 int로 하면 4byte * 10^7이므로 40MB로 초과가 된다.

 

수의 크기가 작으니까 short를 쓸까? short는 2byte이므로 20MB로 여전히 시간초과이다. 이 문제는 수의 범위가 10^4 이하인 자연수라는 점에 초점을 맞춰야한다. 배열을 크게 잡고 갯수를 세는 Counting Sort로 구현하면 된다.

 

Counting Sort의 시간복잡도는 O(n)이므로 5초 시간제한은 무리가 없다. 배열도 int로 선언시 4byte * 10^4 < 1MB 이므로 메모리도 충분하다.

 

 

3. 분석

메모리 초과를 인지하고 Counting Sort로 관점을 바꾸는 것이 핵심이다.