백준 10989번 [수 정렬하기 3](C++)-yes6686- 티스토리

백준 문제 풀이: 10989 [수 정렬하기 3]

---

문제 링크: https://www.acmicpc.net/problem/10989

문제 설명:

자연수 N개가 주어졌을 때, 이를 오름차순으로 정렬하는 문제입니다. 주어진 수는 10,000 이하의 자연수이며, 메모리 제한이 있기 때문에 카운팅 정렬을 사용하여 해결해야 합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

int arr[10001]; // 카운팅 정렬용 배열

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    int x;

    // 입력 숫자를 카운트 배열에 기록
    for (int i = 0; i < n; i++) {
        scanf("%d", &x); // 빠른 입력을 위해 scanf 사용
        arr[x]++;
    }

    // 카운트 배열을 이용하여 정렬된 결과 출력
    for (int i = 1; i <= 10000; i++) {
        if (arr[i] != 0) {
            for (int j = 0; j < arr[i]; j++) {
                cout << i << '\n';
            }
        }
    }

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 카운팅 정렬
• 구현 세부사항:
  • 10,000 이하의 자연수를 저장할 수 있는 카운팅 배열 arr[10001]을 선언합니다.
  • 입력된 각 숫자의 등장 횟수를 배열에 기록합니다.
  • 카운팅 배열을 순회하며, 값이 0이 아닌 경우 그 횟수만큼 해당 숫자를 출력합니다.
• 시간 복잡도: O(N + K)
  • N은 입력 크기, K는 정렬할 값의 범위 (최대 10,000)
• 공간 복잡도: O(K)
  • K 크기의 카운팅 배열이 필요합니다.

---

결과

카운팅 정렬을 사용하여 정렬된 결과를 출력합니다. 이 접근법은 메모리와 시간 제한을 모두 만족하며, 간단히 구현할 수 있는 효율적인 해결책입니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!