[BOJ_C] 10989번

- 문제

10989번 문제

- 풀이

#include <stdio.h>
#include <stdlib.h>

int main(){
    int n;
    scanf("%d",&n);

    int* num = (int*)malloc(sizeof(int)*n);
    for(int i=0; i<n; i++)
        scanf("%d", &num[i]);

    for(int i=0; i<n; i++){
        for(int j=0; j<n-1; j++){
            if(num[j]>num[j+1]){
                int temp = num[j];
                num[j] = num[j+1];
                num[j+1] = temp;
            }
        }
    }

    for(int i=0; i<n; i++)
        printf("%d\n",num[i]);

    return 0;
}

 

처음엔 그냥 아무생각없이 구현이 가장 간단한 버블정렬로 문제를 해결하고자 하였다. 그러나 메모리가 초과되었다는 답을 얻게 되었다. 다른 방법을 찾아보고자 인터넷을 열심히 찾아 보았는데, 그 중 가장 괜찮아 보이는 방법을 가져와 보았다. 

바로 flag를 이용하는 방법이다. 코드는 다음과 같다.

#include <stdio.h>
#include <stdlib.h>

int main(){
    int n, num;
    int flag[10001] = {0, };
    scanf("%d",&n);

    for(int i=0; i<n; i++){
        scanf("%d",&num);
        flag[num]++;
    }

    for(int i=0; i<10001; i++){
        if(flag[i] != 0){
            for(int j=0; j<flag[i]; j++)
                printf("%d\n", i);
        }
    }
    
    return 0;
}

 

해당 숫자에 해당하는 인덱스의 값을 1 증가시켜 주고, 출력할 때, 0이 아닌 즉, 값이 들어있는 인덱스를 출력해주면 오름차순으로 정렬이 된 것과 같은 결과를 얻어낼 수 있다.

 

- 실행결과

실행결과