[BOJ 10989] 수 정렬하기 3 - [정렬]

[BOJ 10989] 수 정렬하기 3 - [정렬]

문제 링크

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

문제 요약

최대 10,000,000개의 수가 주어질 때, 메모리 제한 8MB 내에서 이를 오름차순으로 정렬하여 출력하는 문제 (입력되는 수는 10,000 이하의 자연수).

접근 방법

• 자료구조: 빈도수를 저장할 고정 크기 배열 (int count[10001])
• 알고리즘: 계수 정렬 (Counting Sort)
• 핵심 아이디어: - 메모리 제한이 8MB로 매우 작아 1,000만 개의 숫자를 모두 배열에 저장할 수 없음 ($10^7 \times 4$ bytes $\approx 40$ MB).
  • 입력되는 수의 범위가 10,000 이하라는 점을 이용해 각 숫자의 등장 횟수만 기록하여 출력함.

풀이 코드

#include <iostream>

using namespace std;

// 숫자의 범위가 10,000 이하이므로 빈도를 체크할 배열 선언
// 전역 변수로 선언하여 0으로 자동 초기화 및 넉넉한 스택 공간 확보
int cnt[10001];

int main() {
    // 빠른 입출력을 위한 설정
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;

    // 1. 입력받는 즉시 해당 숫자의 인덱스 값을 증가 (메모리 절약)
    for (int i = 0; i < N; i++) {
        int num;
        cin >> num;
        cnt[num]++;
    }

    // 2. 1부터 10,000까지 순회하며 카운트된 횟수만큼 숫자 출력
    for (int i = 1; i <= 10000; i++) {
        if (cnt[i] > 0) {
            for (int j = 0; j < cnt[i]; j++) {
                cout << i << '\n';
            }
        }
    }

    return 0;
}

시간/공간 복잡도

• 시간 복잡도: $O(N + K)$ (여기서 $N$은 수의 개수 $10^7$, $K$는 수의 범위 $10^4$. 사실상 $O(N)$에 수렴)
• 공간 복잡도: $O(K)$ (범위 $K$만큼의 배열 공간만 필요하므로 약 40KB 소요)

실행 결과

• 메모리: 약 2020 KB (C++ 기준)
• 시간: 약 1400 ~ 2000 ms (서버 상태에 따라 상이)

핵심 포인트

1. 메모리 제한 극복: 모든 데이터를 vector나 array에 push하지 않고 counting 방식만 사용하여 8MB 제한을 통과함.
2. 빠른 입출력: endl 대신 \n을 사용하고 sync_with_stdio(false)를 적용하여 대량의 데이터 처리 속도를 확보함.

예제 확인

• 예제 1: 10개의 수 입력 시, 각 빈도를 계산한 뒤 1 1 2 2 3 3 4 5 5 7 순으로 정상 출력됨을 확인.