[백준] 10989번 수 정렬하기 3 C++ 문제 풀이 정렬

문제

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

입력

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

출력

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

---

예제 입력 1

10

5

2

3

1

4

2

3

5

1

7

---

예제 출력 1

1

1

2

2

3

3

4

5

5

7

---

문제 풀이

#include <iostream>
using namespace std;
int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int N, temp;
    int countArr[10001] = {0,};
    cin>>N;
    for(int i = 0; i < N; i++){
        cin>>temp;
        countArr[temp]++;
    }

    for(int j = 1; j < 10001; j++)
        countArr[j] += countArr[j-1];
    
    int k = 1;
    while(1){
        if(k > 10000)
            break;
        if(countArr[k] > countArr[k-1]){
            cout<<k<<'\n';
            countArr[k-1]++;
        }
        else
            k++;
    }
}

계수 정렬(Counting Sort)로 풀어야 하는 문제입니다.

Counting Sort는 수의 범위가 작을 때 다른 알고리즘보다 빠르게 정렬합니다.

 

계수 정렬 참고 : http://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html

Counting Sort

 

처음에 입력받은 값을 배열에다가 몇 번 들어왔는지 셉니다.

for(int i = 0; i < N; i++){
    cin>>temp;
    countArr[temp]++;
}

그리고 이전 인덱스의 값을 다음 인덱스에다 합하여 누적합을 만듭니다.

for(int j = 1; j < 10001; j++)
    countArr[j] += countArr[j-1];

 

여기까지 완료되면 누적합이 만들어진 배열은 원소와 인덱스의 역할이 바뀌게 되는데

정렬될 배열에는 누적합 배열의 인덱스가 원소로, 원소가 들어갈 위치로 바뀌게 됩니다.

 

그리고 이 방식대로 순회하면 정렬이 됩니다.

int k = 1;
while(1){
    if(k > 10000)
        break;
    if(countArr[k] > countArr[k-1]){
        cout<<k<<'\n';
        countArr[k-1]++;
    }
    else
        k++;
}

오름차순으로 출력해야 하기 때문에 배열의 앞에서부터 순회했습니다.

누적합이 완성된 배열에서 인접 원소 간의 차이는 값의 개수를 나타내기 때문에

해당 개수만큼 출력을 반복하고 같아졌을 경우 k 값을 증가시켜 다음 값을 출력하도록 하였습니다.

 

 

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

10989번: 수 정렬하기 3