10989번 : 수 정렬하기 3

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

10989번: 수 정렬하기 3

 

 

Counting Sort(기수 정렬)을 사용하는 문제이다!

 

기수 정렬에 대한 자세한 설명은 아래 블로그에 잘 나와있다.

https://bowbowbow.tistory.com/8

Counting Sort : 계수 정렬

 

Counting Sort(기수 정렬)

1. cnt 배열을 만들어 빈도수를 저장한다. cnt[수]=수의 빈도수

2. cnt 배열을 누적합으로 만들어 cnt 배열의 값이 각 인덱스와 연관되게 한다.

2. 작은 수부터 큰 수까지 읽어가며 빈도수가 커질때(빈도수가 존재할때) 값을 출력한다.

 

코드

#include <bits/stdc++.h>

using namespace std;
#define count aaa
const int MAX=10000;
int n, temp,count[MAX+4];
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. n개의 숫자 입력받기
    cin >> n;
    for(int i=1;i<=n;i++){
        cin>>temp;
      count[temp]++; //숫자 개수 세기:숫자-숫자개수
    } 
    //2. 누적합 만들기
    for(int i=1;i<=MAX;i++){
        count[i+1]= count[i]+count[i+1]; //인덱스-누적합
    }
    //3. 앞에서부터 빈도수 존재하면 출력
    for(int i=1;i<=MAX;i++){
       while(count[i-1]<count[i]){
          cout << i<<"\n";
          count[i-1]++; //하나씩 출력할때마다 영향을 받지 않는 i-1의 빈도수를 늘려서 i와 같아질때 종료한다. 
      }
    }

    return 0;
}