10989 수 정렬하기 3

어렵다!

 

모르겠다!

 

감도 안 잡힌다!

 

'''

그냥 편하게 정렬해서 풀려 했더니 메모리 초과가 떴다. 보니깐 메모리 제한이 8MB였다ㅋㅋㅋㅋ

8MB = 8 * 1000KB = 8 * 1000 * 1000바이트이고 N은 10,000,000개가 들어온다. 딱 봐도 터진다! 그런데 해결방법을 모르겠다! 알고보니 카운팅 소트를 써야 하는 문제였다. 

 

https://bowbowbow.tistory.com/8

Counting Sort : 계수 정렬

 

전에 수업 자료 찾다가 인덱스가 해당 숫자인 배열 만들어서 풀길래 나도 그냥 해당 인덱스의 숫자가 몇 번 나오는지 확인하도록 했는데 알고보니 위의 링크가 카운팅 소트였다ㅋㅋㅋ 

 

카운팅 소트는 각 숫자가 몇 번 나오는지 세어주고 이걸 누적으로 더해준다. 그리고 이 배열을 참고해서 위치를 다시 지정해준다. 

 

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

int main() {
    int n;
    scanf("%d", &n);
    vector <int> a(10001, 0); 
    
    for(int i = 0; i < n; i++){
        int input;
        scanf("%d", &input);
        a[input]++;
    }
    for(int i = 1; i < 10001; i++){
        if(a[i] != 0){
            for(int j = 0; j < a[i]; j++)
                printf("%d\n", i);
        }
    }
    
    return 0;
}

 

나는 이런 식으로 짰다.ㅋㅋㅋ 이게 카운팅 소트가 아니었구나; ; 머쓱

 

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

int main() {
    int n;
    scanf("%d", &n);
    vector <int> a(n+1); 
    vector <int> b(n+1); 
    vector <int> count(10001, 0);
    
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        count[a[i]]++;
    }
    for(int i = 1; i < 10000; i++){
        count[i+1] += count[i];
    }
    for(int i = n; i > 0; i--){
        int index = a[i];
        b[count[index]] = a[i];
        count[a[i]]--;
    }
    for(int i = 1; i <= n; i++){
        printf("%d\n", b[i]);
    }
    return 0;
}

ㅋㅌㅎㅋㅋ 카운팅 소트는 구현했는데 터졌다. 그리고 원래 코드가 좋긴 더 좋아보인다 ~.~ 위에껄로 해야지

 

---

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

int main() {
    int n;
    scanf("%d", &n);
    vector <int> a(10001, 0); 
    
    for(int i = 0; i < n; i++){
        int input;
        scanf("%d", &input);
        a[input]++;
    }
    for(int i = 1; i < 10001; i++){
        for(int j = 0; j < a[i]; j++)
            printf("%d\n", i);
    }
    return 0;
}

오 이렇게 푸는 것도 보통 카운팅 소트라 한다. 이전 코드에 a[i]가 0이 아닐 때 돌게 조건문 달았는데 a[i]가 0이면 for문 자체가 안 돌아서 없애도 된다ㅋㅋㅋ