[BOJ 2750, 2751, 10989] 수 정렬하기 / 수 정렬하기 2 / 수 정렬하기 3

1) 문제 링크

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

2) 접근

2750번은 N의 범위가 [1, 1000]이니까 1초 제한 맞추려면 그냥 O(NlogN)짜리인 std::sort() 돌려도 된다.
근데 2751번, 10989번은 각각 [1, 1000000], [1, 10000000]인데 제한시간이 2초, 3초니까 적어도 O(N)에 준하는 수준의 다른 방법을 생각해야 된다. 여기서 핵심은 데이터들이 모두 정수라는 것! 이때는 counting sort(카운팅 정렬)을 쓸 수 있다. 아래 소스코드들은 세 문제 모두 counting sort를 사용하여 푼 코드이다.

3) 풀이

// 2750
#include <iostream>

using namespace std;

int main()
{
    int N, num;
    int check[2001] = {0, };

    cin >> N;
    for(int i=0; i<N; ++i){
        cin >> num;
        ++check[num+1000];
    }

    for(int i=0; i<=2000; ++i){
        if(check[i]){ cout << i-1000 << '\n'; }
    }
    return 0;
}

// 2751
#include <iostream>
using namespace std;

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

    int N, num;
    int check[2000001] = {0, };

    cin >> N;
    for(int i=0; i<N; ++i){
        cin >> num;
        ++check[num+1000000];
    }

    for(int i=0; i<=2000000; ++i){
        if(check[i]){ cout << i-1000000 << '\n'; }
    }
    return 0;
}

// 10989
#include <iostream>
using namespace std;

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

    unsigned int N;
    int num, check[10001] = {0, };

    cin >> N;
    for(unsigned int i=0; i<N; ++i){
        cin >> num;
        ++check[num];
    }

    for(int i=1; i<=10000; ++i){
        for(int j=0; j<check[i]; ++j) { cout << i << '\n'; }
    }
    return 0;
}

4) 피드백

(특히나 2751번 문제) 굉장히 낮은 시간 내에 처리하는 Goat 들의 코드를 보면 Buffer니 뭐니 하면서 의미 자체가 이해 안 되는 코드들이 많다. 뭔가 low한 부분을 건든 거 같은데, Goat들의 블로그나 설명을 들어볼 필요가 있을 듯…