백준 10989번: 수 정렬하기 3

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

---

1) 처음에는 수의 개수가 (1 ≤ N ≤ 10,000,000) 만큼이라고 하길래 단순하게 생각해 int arr[10000000] 를 전역변수로 만들고 C++의 sort()함수를 이용해 코드를 짰다.

그랬더니 메모리 초과가 떴다.

2) 배열의 크기를 어떻게 줄일까 생각하다가, 입력받는 수가 10,000보다 작거나 같은 자연수라는 조건을 보고 한 가지 다른 방법이 생각났다.

입력 받은 숫자를 일일이 배열에 넣는 것이 아니라 수의 개수를 저장하는 방법이다.

아래의 성공 코드와 알고리즘은 똑같지만 두 번째 시도에선 C++의 cin과 cout을 이용해 구현을 했었는데, 그랬더니 시간 초과가 떴다.

3) 다른 문제를 풀 때도 C언어가 항상 가장 빨랐던 기억이 있어 혹시나 하는 생각에 C언어로 scanf와 printf를 사용해 제출하니 맞았습니다! 를 받을 수 있었다.

⭕️ 풀이 코드 - 성공

헉 이제보니 입력 받는 자연수의 범위는 10,000까지인데 나는 100,000만큼 10배를 더 할당했었네... 운 좋게 정답이 됐다.

#include <stdio.h>

int main() {
    int arr[100001] = {0}; // 초기화
    int n, temp;
    scanf("%d", &n);
    
    // 숫자를 입력 받고 해당 배열을 1 증가 시킨다
    for(int i=1; i<=n; i++) {
        scanf("%d", &temp);
        arr[temp]++;
    }
    
    for(int i=1; i<=100000; i++) {
        for(int j=1; j<=arr[i]; j++) {
            printf("%d\n", i);
        }
    }
    
    return 0;
}

cin, cout, scanf, printf 는 왜 차이가 나는 걸까!?

백준의 질문 게시판을 찾아보니 cin과 cout이 scanf와 printf보다 느리고, endl 또한 버퍼를 flush(비우는)하는 역할을 겸하기 때문에 \n 보다 매우매우매우 느리다고 한다.

std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);

해결 방법으로는 main() 함수 안에 위 코드를 넣고 cin과 cout을 사용하면 scanf와 printf보다도 빨라진다.

참고 : ios_base::sync_with_stdio(false); cin.tie(null); 구문을 추가해주는 이유

관련 알고리즘 : Counting Sort

이름 그대로 각 숫자가 몇 번 등장했는지 세어주는 방법이다.

Counting Sort 는 정렬 알고리즘으로 $O(n)$의 시간 복잡도를 갖는다.

Conting Sort에 대해 정리한 게시물 추가 예정.