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

문제: www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

 

문제풀이

 

처음 문제를 접근한 방식은 N 크기의 배열을 만든 후 sort() 함수를 이용해 배열을 정렬 후 출력하려고 했다.

하지만 문제가 요구하는 최대 메모리의 크기는 8MB이기 때문에 메모리 초과로 정답을 맞히지 못했다.

 

다시 문제를 살펴보고 입력되는 숫자가 "10,000보다 작거나 같은 자연수" 인 것을 확인하고 배열 인덱스를 이용하여 문제를 풀었다.

 

10,000 크기의 배열을 선언, 0으로 초기화한 후 입력되는 숫자를 인덱스로 가진 배열을 증가시켜 해당 숫자의 개수를 기록했다.

 

 

코드

#include <iostream>

using namespace std;

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

    int N;
    cin>>N;

    int num;
    int arr[10000] = {0,}; //10,000 크기 배열 0으로 초기화
    for(int i=0; i<N; i++){
        cin>>num;
        arr[num-1]++; //입력되는 숫자를 인덱스로 가진 배열 증가
    }


    for(int i=0; i<10000; i++){
        while(arr[i]--)
            cout<<i+1<<"\n"; //개수만큼 출력
    }

    return 0;
}

 

 

결과