[C++] 백준 10989 : 정렬의 다른 접근방법 (Counting)

 

편의점에서 야간 근무 중 한산한 시간에 백준을 들어갔다가, 재미있는 문제를 풀어서 글을 써봅니다.

어렵지는 않은데 접근법을 달리하는 것이 저난도 PS의 재미인 것 같습니다.

 

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

 

 

정렬 문제인데 일반적인 vector<>와 sort()를 사용하는 접근법이 불가능한 문제입니다.

그 이유는 입력 조건에 있습니다.

 

• 데이터 개수가 총 천만(10,000,000)건
• 메모리 제한 8mb
• 각 요소는 10,000 이하 자연수

단순 계산으로 천만 건의 데이터를 8mb 안에 담는 것은 불가능합니다

 

int    : 4byte * 10,000,000 = 40mb

shrot: 2byte * 10,000,000 = 20mb

 

byte형 또한 10mb에 달하는 것과 동시에 unsigned를 사용하여도 512까지 표현가능하니 사용할 수 없습니다. 따라서 일반적인 sort 대신 다른 접근을 하여야 합니다. 힌트는 위의 조건에 있는데, 데이터가 "천만 건"씩이나 되지만 그 범위는 "1부터 10,000까지"라는 것입니다.

 

잘 생각해보면, 우리가 정렬을 할 때 비교를 해서 위치를 바꾸는 복잡한 과정을 하는 이유는, 앞의 값과 뒤의 값이 어떤 값이 올지 알 수 없기 때문입니다. (21억 4700만이 올지 0이 올지 그 범위를 알 수 없습니다.) 그런데 1부터 10,000까지로 제한이 되었다면 비교 대신 개수를 세는 방법으로 대체가 가능합니다.

 

아래 계수 정렬(Counting Sort)에 대해 잘 설명해주신 다른 분 글이 있어 링크를 첨부합니다:

https://jeonyeohun.tistory.com/103

[알고리즘 정리] 계수정렬(Counting Sort)

 

 

여기까지 도달했다면 다음은 간단합니다. 1부터 10,000까지의 수가 각각 몇 번 나왔는지 세어서, 각 숫자를 나온 횟수만큼 출력해주면 됩니다. 1이 10번이 나왔다 하여도 그 10개의 1은 모두 같은 1이므로, 입력 받은 후 count[num]++ 형태로 처리하면 되겠습니다.

 

백준의 문제 특성 상 입력을 스토리지에 저장해둘 필요도 없고, 출력 또한 콘솔에 찍으면 그만이기에 별도의 저장 배열은 필요 없습니다. Count 배열만 메모리에 할당하여 표준 입력을 받을때 증가연산, 입력을 다 받으면 반복문을 통해 출력을 하면 되겠습니다. 정렬이라 하면 일반적으로 입력 받은 후 정렬된 것을 저장하는데, 이번 문제같은 경우 저장 없이 횟수만 저장하기에 제목을 Counting이라고 표현하였습니다.

 

아래는 그 코드입니다.

개수를 저장하는 배열은 arr로 선언하였습니다. (모두 0으로 초기화하는 번거로운 작업을 생략하기 위해 전역 배열로 선언하였습니다.) 등장 횟수가 0번인 수는 출력하지 않아야 하는데, 이는 for-loop 조건에서 걸러집니다. (2중 loop 중 j 부분) 

#include <iostream>

#define endl '\n'

using namespace std;

int arr[10001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int size;
    int temp;
    cin >> size;

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

    for (int i = 1; i <= 10000; i++) {
        for (int j=0; j<arr[i]; j++)
            cout << i << endl;
    }

    return 0;
}