[백준] 10989 수 정렬하기 (C++)

 

 

입출력

---

풀이

 

#include <iostream>

using namespace std;

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

    int cnt;
    cin >> cnt;

    int arr[10001] = {};
    int n;
    for (int i = 0; i < cnt; i++) 
    {
	cin >> n;
        arr[n] += 1;
    }

    for (int i = 1; i <= 10000; i++)
        for (int j = 0; j < arr[i]; j++)
            cout << i << "\n";
}

---

계수 정렬을 이용한다

 

n을 입력 받아서 arr[n]에 1을 채워넣는다

그 후에 1이 들어가있는 arr[]만 차례대로 출력하면 오름차순으로 정렬되어있는 배열이 완성된다 !

 

입력이 5, 4, 7, 6, 1일때 arr[]는 아래 그림처럼 채워진다