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

1. 문제

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

10989번: 수 정렬하기 3

 

 

2. 풀이과정

일반적인 정렬문제가 시간 제한과 메모리 제한을 고려해야하는 문제이다.

생각 1

10,000,000 크기의 배열을 선언하여 정렬 알고리즘을 수행한다면

10,000,000 x short 자료형(2byte) = 20,000,000 byte이다.

1 MB = 1024KB = 1024 x 1024 Byte (단위가 바뀔때 마다 2의 10제곱씩 커진다.)

따라서 20,000,000 byte = 19.07 MB이므로 문제의 메모리 제한 조건을 훨씬 넘어선다.

 

생각 2

10,000,000 크기의 배열의 정렬로는 불가능하다고 판단, 다른 방법으로 접근하였다.입력받는 수가 자연수 10,000이하이기 때문에 각 수를 인덱스로 하여 갯수 저장하고 출력하기로 했다.

 

1. int형 배열로 크기 10,000의 배열을 0으로 초기화 하여 선언한다.

 

2. 각 입력받은 수의 - 1을 인덱스로 하여 값을 증가 시켜 주었다.

arr[num-1]++;

 

3. 10000번 반복하면서 arr[] 배열의 값만큼 해당 인덱스를 출력한다.

 

4. 추가로 시간제한을 고려하여 아래의 코드를 추가한다.

ios_base::sync_with_stdio(false);   
cin.tie(NULL);

ios_base::sync_with_stdio(false);   

기본적으로 c++은 표준 입출력 함수와 표준 입출력 스트림을 동기화 시키지만 이 동기화가 입출력 성능을 낮출 수 있다. 따라서 이를 분리한다.

cin.tie(NULL);

cin은  cout과 묶여 있다. 이는 cin으로 입력받을때 마다 자동으로 cout을 비우게 된다. 그러나 이 동작이 입출력 속도를 늦추기에 이를 분리시켜 주어 cin마다 cout을 초기화하는 동작을 하지 않도록 한다.

 

 

3. C++ 정답코드

#include <iostream>
using namespace std;

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

    int n;
    cin >> n;
    const int arrSize = 10000;
    int arr[arrSize] = {0};
    int num;
    for (int i = 0; i < n; i++)
    {
        cin >> num;  
        arr[num-1]++; //인덱스 0부터 저장
    }
    for (int i = 0; i < arrSize; i++)
    {
        for (int j = 0; j < arr[i]; j++)
            cout << i+1 << '\n';
    }
    return 0;
}