[백준(BOJ)] 10989번: 수 정렬하기 3 (정렬, C++)

📄 문제풀이 과정

---

단순히 정렬하는 문제인줄 알고 qsort를 사용하려고 했으나, 메모리초과가 발생했다. 

메모리 사용은 최대 8MB까지로, 메모리 사용에 유의해야 한다.

일반적으론 배열에 모든 입력을 저장해서 sorting을 진행하지만, 이 문제에선 메모리 문제를 해결하기 위해서는 배열에 입력 값을 저장하면 안 된다. 따라서 입력받을 때마다 해당 수를 인덱스로 해당 수에 대한 카운팅을 하도록 했다. 그럼 각 인덱스마다 수가 몇 번 나타나는지 알 수 있으므로 출력 시 인덱스에 대한 값만큼 반복하여 인덱스 값을 출력하도록 했다. 해당 sorting 방법은 카운팅 정렬 알고리즘이다.

또 주의할 점은, 배열 크기는 입력받는 값인 N이지만, 배열 크기를 N으로 잡거나 출력 시 N만큼 반복문을 돌리면 메모리초과 에러가 발생한다. 1 ≤ N ≤ 10,000,000 인데, 수의 범위는 10,000보다 작거나 같은 자연수이므로 배열의 크기는 10,000 인덱스까지만 담을 수 있으면 되고, 출력 시에도 10,000 범위의 수만 고려하면 된다.

 

 

💻 코드

---

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N;
    scanf("%d", &N);
    int count[10001]={0,};
    
    for(int i=0; i<N; i++){
        int num; scanf("%d", &num);
        count[num]++;
    }
    
    for(int i=0; i<10001; i++){
       for(int j=0; j<count[i]; j++) printf("%d\n", i);
    }  
}

 

 

🖨 제출 결과

---