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

 

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

 

💣 메모리 초과

 

메모리 제한이 8MB인게 핵심인 문제다. 퀵 정렬 시도하자마자 바로 컷 당해버렸다!

계수 정렬을 이용하는 문제이다. 카운팅 소트Counting Sort라고도 한다.

⭐ 그리고 입력받는 자연수들을 굳이 배열로 저장하여 갖고있을 필요도 없다! ⭐

최대 1,000,000개의 값이 들어오는데 이 값들을 전부 배열에 저장하면 메모리 초과!

 그 후 시간 초과, 출력 초과도.. 마주쳤는데.. 원인과 해결방법은 아래 풀이와 함께 참고하자.

 

 

✒ 카운팅 정렬의 원리

 

카운팅 정렬은 흥미롭게도 비교 기반 정렬 알고리즘이 아닌 정렬 알고리즘이다. 

카운팅 정렬에서 카운트 배열을 사용하는 이유는, 주어진 배열의 각 원소의 출현 빈도를 기록하여 원소들이 어디에 배치될지를 결정하기 위함이다.

 

 

카운팅 소트는 처음 구현해봤지만.. 매우 흥미로운 알고리즘이었다.

 

 

---

 

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

 

 

 

 

 

입출력 예시

입출력 예시

 

입출력 예시

 

 

 

---

 

풀이 

계수 정렬의 시간 복잡도와 공간 복잡도는 모두 O(n + k)로, n은 입력 배열의 크기, k는 값의 범위를 뜻한다.

 

처음엔 입력받은 값들을 모두 배열에 저장해서 계수 정렬을 시도했지만, 

문제에서 입력 받는 값이 최대 10,000,000개이기 때문에, 이 값들을 저장하는 것만 해도 8MB를 훌쩍 넘는다.

따라서, 입력값을 저장하지 않고 바로바로 카운팅 배열로 처리하도록 했다.

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(NULL);
    
    int N;
    cin >> N;

    /* 카운트 배열 채우기 */
    vector<int> count(10000, 0);
    for (int i = 0; i < N; ++i) {
        int n;
        cin >> n;
        count[n]++;
    }

    for(int i = 1; i <= count.size(); ++i) {
        if (count[i] > 0) {
            for (int j = 0; j < count[i]; ++j) 
                cout << i << "\n";
        }
    }

    return 0;
}

 

 

💀 메모리 초과

메모리 초과의 원인이었던 코드이다.

/* 입력 배열 저장해서 정렬하는 방법. */

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

void countingSort(vector<int>& arr) {
    /* 배열의 최소값, 최대값 */
    int max = *max_element(arr.begin(), arr.end());
    int min = *min_element(arr.begin(), arr.end());

    int range = max - min + 1;
    vector<int> count(range, 0);

    ...
}

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

    int N;
    cin >> N;

    vector<int> nums(N);
    for (int i = 0; i < N; ++i) {
        cin >> nums[i];
    }

    countingSort(nums);

    for(int n : nums) {
        cout << n << "\n";
    }

    return 0;
}

 

 

💀 시간 초과

시간 초과 문제를 해결하기 위해 아래 코드를 추가했다.

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);

 

 

 

💀 출력 초과

    for(int i = 1; i <= count.size(); ++i) {	// count.size()가 아닌 N으로 작성하면 출력 초과가 뜸.
        if (count[i] > 0) {
            for (int j = 0; j < count[i]; ++j) 
                cout << i << "\n";
        }
    }

 

---