백준 10989 - 수 정렬하기 3

문제 설명

 

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

=> 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;
}

 

 

 

실행화면 

---

 

=> 9달전과 3달 전에는 아무리 이해하려 해도 안되던 문제가 결국 해결되었습니다.