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

문제

 

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

 

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

 

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

 

입력

 

10
5
2
3
1
4
2
3
5
1
7

 

출력

 

1
1
2
2
3
3
4
5
5
7

 

풀이

 

이번에도 수를 정렬하는 문제이다. 수 정렬하기 2번과 크게 다를건 없다. 단지 메모리 제한을 제외하고는 말이다.

 

 

 

이런식으로 메모리에 제한이 걸려있다. 하지만 일단 아무 생각없이 2에서 사용했던 힙을 사용해보니 당연하게도 메모리에서 걸렸다.

 

하지만  사실은 이 문제도 처음에 제목에서 어떤 문제인지 알려준다.

 

 

바로 카운팅 정렬이라는 것을 사용해야 한다. 카운팅 정렬이란 전체 숫자에서 각 숫자의 빈도 수를 구한 다음 차례대로 빈도수 만큼 출력하는 것을 말한다.

 

위의 예시로 풀이를 해보자면 5 2 3 1 4 2 4 5 1 7의 숫자들이 있다. 여기서 각 숫자의 빈도수를 계산하여 배열에 집어 넣는다.

 

0	1	2	3	4	5	6	7
0	2	2	1	2	2	0	1

 

이렇게 빈도수를 구 할 수 있다. 그리고 이 빈도수를 토대로 0에서 순차 탐색을 진행하면 된다.

 

0은 빈도수가 0, 패스

1은 빈도수가 2, 1을 두 번 출력

2는 빈도수가 2, 2를 두 번 출력

3은 빈도수가 1, 3을 한 번 출력

4는 빈도수가 2, 4를 두 번 출력

5는 빈도수가 2, 5를 두 번 출력

6은 빈도수가 0, 패스

7은 빈도수가 1, 7을 한 번 출력

 

이걸 순서대로 적으면 1 1 2 2 3 4 4 5 5 7로 자동으로 정렬되는 것을 볼 수 있다. 이것을 응용해서 누적합 방식으로도 카운팅 정렬이 사용가능하다.

 

 

0	1	2	3	4	5	6	7
0	2	4	5	7	9	9	10

 

이렇게 누적합으로 계산을 하면 1은 1, 0/ 2는 3, 2/ 3은 4 이런식으로 누적합 - 1 에서 부터 전 숫자가 있을 때까지로 범위를 지정하여 누적합으로도 계산이 가능하지만 메모리 때문인가 누적합으로 풀이를 진행하니 안되더라...

 

그래서 위의 방식으로 진행했다.

 

코드

 

#include <iostream>

using namespace std;

int main(void){
    int counting_array[10001] = {0,}, n;
    scanf("%d", &n);

    for(int i = 0 ; i < n ; i++){ //1. 수열의 배열을 초기화
        int temp;
        scanf("%d", &temp);

        counting_array[temp]++; //각 값들을 누적
    }

    for(int i = 0 ; i < 10001; i++){
        for(int j = 0 ; j < counting_array[i]; j++){
            printf("%d\n", i);
        }
    }
    return 0;
}

 

굉장히 코드가 간략하다. 처음에는 빈도수 배열, 인덱스 배열, 최초 배열 등 여러개의 배열을 만들다 실패를 해서 다시 곰곰히 생각해서 배열을 최소한으로 줄여서 문제를 풀이 하였다.

 

배열을 많이 만든 이유가 for문을 중첩시키지 않고도 충분히 풀 수 있을 거라고 생각했는데 결국 이 문제에서 해결해야하는 부분은 시관초과가 아니라 메모리였기 때문에 크게 연연하지 않아도 되는 부분에 너무 연연했던 것 같다.