백준 10989 - 수 정렬하기 3

백준 algorithm

백준 10989 - 수 정렬하기 3

cosmohoo 2020. 7. 9. 12:49

=> 구현 카테고리에 있지만, 구현 문제가 아닌 것 같습니다.

=> vector에 넣어 sort 함수를 사용할 경우 시간제한과 메모리 제한에 걸리게 됩니다.

=> 해당 문제를 해결하기 위해서는 기존의 문제들과는 다른 시선이 필요합니다.

arr [10001]arr [10001] : 주어지는 수는 10000 아래의 수입니다. 그러므로 해당 숫자가 몇 개가 들어가는지 확인하는 배열을 선언합니다.
max : 출력할 때, 쓸데 없는 부분까지 탐색하는 문제를 해결하기 위해 max 변수를 선언하여 사용합니다.
arr 배열에는 실제 수가 아닌 해당 index 수가 몇 번 나왔는지를 세어줍니다.
0부터 max까지의 수중 1개 이상의 갯수를 가진 index를 차례대로 출력해줍니다.

=> 위와 같은 방법으로 논리를 구성하여 코드를 짜면 풀 수 있는 문제입니다.

<code>

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>

using namespace std;

int arr[10001]={0};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int N;
    int tmp = 0;
    cin >> N;
    
    int max =0;
    for(int i=0; i<N; i++)
    {
        int tmp;
        cin >> tmp;
        arr[tmp]++; //index 숫자의 갯수 추가
        if(tmp > max) max= tmp;
    }
    
    for(int i=0; i<=max; i++)
    {
        for(int j=0; j<arr[i]; j++)
        {
            cout<<i<<'\n';
        }
    }
  
    return 0;
}