C++ 코딩테스트 강좌, 022 수 정렬하기 3

문제 설명:
“수 정렬하기 3” 문제는 주어진 숫자들을 정렬하는 문제로, 입력하는 수의 범위가 제한되어 있습니다. 특히, 이 문제의 입력 범위는 1부터 10000까지의 정수이며, 각 정수의 개수는 매우 많을 수 있습니다. 따라서, 우리는 단순한 정렬 알고리즘을 사용하는 대신, 보다 효율적인 방법을 모색해야 합니다. 이 문제는 카운팅 정렬(Counting Sort) 알고리즘을 활용하여 해결할 수 있습니다.

문제의 조건

입력 받는 수의 개수: N (1 ≤ N ≤ 100000)
수의 범위: 1 ≤ 수 ≤ 10000

알고리즘 설명

카운팅 정렬 알고리즘은 정수 값을 정렬하기 위해 주어진 값의 범위를 기준으로 배열을 만들고, 개수를 계산하여 정렬하는 방식입니다. 그 과정은 다음과 같습니다:

입력할 수의 최대값을 기준으로 배열을 생성한다. 이 경우, 최대값은 10000이다.
입력할 수의 개수 N만큼 반복하면서, 각 수의 개수를 카운팅 배열에 저장한다.
카운팅 배열을 이용하여 각 수를 그 수의 개수만큼 출력한다.

이 방법은 O(N + K)의 시간 복잡도를 가지며, K는 수의 범위 (여기서는 10000)입니다. 따라서 입력 데이터가 많더라도 효율적으로 처리할 수 있습니다.

문제 풀이 과정

입력을 받기 위해 필요한 헤더 파일을 포함한다.
정렬할 숫자의 개수 N을 입력받는다.
수의 개수를 저장할 카운팅 배열을 선언하고, 0으로 초기화한다.
N개의 수를 입력받으면서, 해당 숫자의 인덱스에 1을 추가하여 개수를 세는 반복문을 만든다.
개수가 카운팅된 배열을 참조하여, 각 숫자를 그 수의 개수만큼 출력하는 반복문을 만든다.

C++ 코드


#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n; // 숫자의 개수 입력받기
    vector count(10001, 0); // 1부터 10000까지의 수의 개수를 저장할 배열

    // 수 입력받아서 카운팅
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        count[num]++;
    }

    // 카운팅된 배열을 기반으로 정렬된 수 출력
    for (int i = 1; i <= 10000; i++) {
        while (count[i] > 0) {
            cout << i << '\n';
            count[i]--;
        }
    }

    return 0;
}

위 코드 설명

1. 입력: 사용자로부터 정렬할 수의 개수 N과 N개의 정수를 입력받습니다.

2. 카운팅 배열 생성: 카운팅 정렬을 위해 10001 크기의 벡터를 생성합니다. 이 배열의 인덱스는 입력받은 수를 의미하며, 각 인덱스의 값은 해당 숫자의 개수를 저장합니다.

3. 수 카운팅: N개의 수를 반복하여 카운팅 배열의 해당 인덱스를 증가시킵니다. 이를 통해 각 숫자의 빈도를 세는 것입니다.

4. 출력: 카운팅된 결과를 바탕으로, 각 숫자를 빈도만큼 출력합니다. 이 과정에서 각 숫자의 인덱스가 해당 숫자를 식별하게 됩니다.

효율성 분석

이 알고리즘은 시간 효율성이 뛰어나, 최대 100000개의 수를 가진 데이터셋도 문제없이 처리할 수 있습니다. 메모리 측면에서도 카운팅 배열은 10001의 고정 크기로 메모리를 추가로 소모하지 않으므로, 전반적으로 좋은 성능을 보입니다.

종합 정리

카운팅 정렬을 사용하여 “수 정렬하기 3” 문제를 해결하는 과정은 분명 효율적이며, 특히 입력값의 범위가 제한되어 있는 특성이 이 방법의 유용성을 강조합니다. 이 문제를 통해 카운팅 정렬의 개념을 잘 이해할 수 있으며, C++의 벡터를 활용하여 데이터 구조와 알고리즘을 결합하는 방법에 대해 학습할 수 있습니다.

심화 내용 및 응용

카운팅 정렬은 특정 상황에서 매우 효율적이지만, 모든 정렬 문제에 적합하지 않는다는 점을 명심해야 합니다. 이 알고리즘은 정수 또는 열거형 데이터를 정렬할 때에만 사용할 수 있으며, 실수와 같이 범위가 넓은 데이터를 다룰 때는 다른 알고리즘(예: 퀵 정렬, 병합 정렬 등)을 고려하는 것이 좋습니다.

또한, 카운팅 정렬은 수의 범위가 작을 때에 가장 큰 장점을 가지므로, 이러한 특성을 가진 문제에서는 항상 고려해야 할 정렬 알고리즘 중 하나입니다.

결론: “수 정렬하기 3” 문제는 카운팅 정렬을 통해 손쉽게 해결할 수 있는 예시입니다. 이 강좌를 통해 C++ 코딩 능력을 한층 더 발전시킬 수 있기를 바랍니다!