10989번: 수 정렬하기 3

 

- 관련 사이트: https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

"수의 범위가 작다면 카운팅 정렬을 사용하여 더욱 빠르게 정렬할 수 있습니다."

 

문제의 내용은 "2751번: 수 정렬하기 2"와 동일하다.

하지만, 동일 로직을 사용할 경우, 시간 초과 되어 다른 방법을 사용해야만 한다.

따라서, 힌트에 주어진 것처럼 카운팅 정렬 (Counting Sort) 을 이용하여 문제를 해결하였다.

 

1) 최대 개수 + 1만큼의 배열 생성 및 0으로 초기화

2) 배열[입력된 값] ++

3) 배열 1번부터 끝번까지 for 문 수행

4) 배열에 있는 값이 0이 아닐 경우, 배열의 index를 저장된 값만큼 표출

 

#include <iostream>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, n;
    int size = 10001;
    int nums[size];
    fill_n(nums, size, 0);
    
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> n;
        nums[n]++;
    }

    for (int i = 1; i < size; i++)
    {
        int num = nums[i];
        for (int cnt = 0; cnt < num; cnt++)
            cout << i << "\n";
    }
    return 0;
}

- 메모리: 2020 KB

- 시간: 1724 ms

- 코드 길이: 465 B

 

 

* 이론 정리

- 카운팅 정렬 (Counting Sort)

 

* 연관 문제

- 2750번: 수 정렬하기

- 2751번: 수 정렬하기 2

- 11650번: 좌표 정렬하기

- 11651번: 좌표 정렬하기 2