백준 10989_수 정렬하기3 [C++]

문제

 

 

풀이

 이 문제는 수 정렬을 하는 것은 동일하게 진행하는 문제이나, 시간과 메모리에 제한이 있기때문에 '수 정렬하기' 문제와 같이 풀이를 진행할 수 없습니다. 따라서 이 문제의 해결을 위해서는 단순히 값을 비교하는 과정을 반복하거나 sort 함수를 사용하는 방법외에 다른 방법으로 문제를 접근해야 한다는 것을 알 수 있습니다.

 문제를 읽어보면 10000보다 작은 범위의 자연수라는 조건이 있습니다. 따라서 크기가 10000인 배열을 선언해주고, 입력받은 값이 n일 경우 arr[n]의 값을 1증가 시켜주고, 크기가 10000인 배열의 값에 따라 해당 순번을 카운트 된 값만큼 반복해주면 됩니다. 소스코드는 아래와 같습니다.

 

 

소스코드

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

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

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