10989번 : 수 정렬하기 3

문제는 다음과 같습니다.

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

풀이 코드는 다음과 같습니다.

#include <string>
#include <iostream>
using namespace std;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int arr[10001]={0};
  int n;
  cin>>n;
  for(int i{0};i<n;i++)
    {
      int temp;
      cin>>temp;
      arr[temp]++;
    }
  for(int i{1};i<10001;i++)
    {
      if(arr[i])
      {
        for(int j{0};j<arr[i];j++)
          {
            cout<<i<<"\n";
          }
      }
    }
  return 0;
}

 

제한에도 나와있지만 시간을 굉장히 넉넉하게 주는 것 처럼 보이지만 함정입니다.

하지만 주어지는 수의 개수가 주어진 메모리보다 훨씬 많은 양입니다.

10000보다 작은 자연수이니 4 byte인 int로 값을 받아도 10,000,000개씩 값을 저장하게 되면

40,000,000byte = 40MB 입니다. 흔히 사용하는 자료형 중 가장 작은 char를 사용해도 10MB를 넘깁니다.

여기서 주어지는 힌트는 10,000,000개의 수 모두 10000이하의 값이라는 것입니다. 따라서 모든 값을 저장하지 않고 1부터 10000까지 나온 수를 카운트하여 그만큼 출력하는 방법을 사용해주었습니다.

그래도 수가 큰 만큼 ios::sync_with_stdio / cin.tie 도 사용하였으며 값을 출력할 때에도 endl 대신 \n을 사용하였습니다.