BOJ - 10989 - 수 정렬하기 3

문제

10989번: 수 정렬하기 3

SOL

• 데이터의 개수가 1 ~10,000,000개 주어진다.
  • O(N * log N) 사용 - 데이터가 방대하다.
• 데이터의 범위는 10,000 보다 작거나 같은수다.
  • 계수정렬(Counting Sort) - 범위가 다소 작다.

구현

#include<iostream>
using namespace std; 

// 데이터의 개수 입력 후 데이터 입력 하기  
// 카운팅할 배열 선언 
// 카운팅 하기 
// 카운팅 한 배열 출력 

int main()
{   
    // counting arr 
    int arr[10001]={0}; 
    int num;
    int tmp;

    // 데이터 입력 
    cin >> num;
    for(int i=1; i <= num; i++)
    {
        scanf("%d", &tmp);
        arr[tmp]++;
    }
    // 결과 출력
    for(int i=1; i < 10001; i++)
        while(arr[i] != 0)
        {
            cout << i << '\n';
            arr[i]--; 
        }       
    return 0;
}

입력을 받을 때 std::cin, cout 보다 scanf, printf가 더 빠르다.

사람들이 C 형식으로 푸는것은 다 이유가 있구나라는 생각이 든다.

std::cin, cout 사용

#include<iostream>
using namespace std; 

// 데이터의 개수 입력 후 데이터 입력 하기  
// 카운팅할 배열 선언 
// 카운팅 하기 
// 카운팅 한 배열 출력 

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

    // counting arr 
    int arr[10001]={0}; 
    int num;
    int tmp;

    // 데이터 입력 
    cin >> num;
    for(int i=1; i <= num; i++)
    {
        cin >> tmp;
        arr[tmp]++;
    }
    // 결과 출력
    for(int i=1; i < 10001; i++)
        while(arr[i] != 0)
        {
            cout << i << '\n';
            arr[i]--; 
        }       
    return 0;
}

물론 위와 같은 방법으로 std::cin, cout을 가속화 하여 쓸 순 있지만 일종의 편법이라 하니 되도록 효율성을 높일 땐 C스타일의 코딩법을 생각해보자.

Reference

글 읽기 - 추가 설명 및 다른 언어 빠른 입출력 방법