B_10989

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

10989번: 수 정렬하기 3

문제가 주어졌을 때, 이전 문제(수 정렬하기 2)의 결과가 시간 초과였다.

(Sort를 사용해도 괜찮았겠지만, 뭔가 배운 내용을 응용하고 싶었다.)
해서, 자연스럽게 모든 테스트케이스에서 nlogn의 시간을 보장하는 mergeSort를 이용하여 풀고자 했지만 메모리 초과가 나왔다.
합병 정렬의 공간 복잡도는 n이다. 그렇다면 n보다 작은 공간 복잡도를 만든느 방법이 필요하다.

 

[에러가 발생한 C++ 코드]

#include <iostream>
#include <vector>
#define Max 1000001

using namespace std;

int N, arr[Max];
int *sorted;

void merge(int left, int right)
{
    int mid = (left + right) / 2;
    int i = left;
    int j = mid + 1;
    int k = left;

    while (i <= mid && j <= right)
    {
        if (arr[i] <= arr[j])
            sorted[k++] = arr[i++];
        else
            sorted[k++] = arr[j++];
    }

    int temp = i > mid ? j : i;

    while (k <= right)
        sorted[k++] = arr[temp++];
    for (int i = left; i <= right; i++)
        arr[i] = sorted[i];
}

void partition(int left, int right)
{
    int mid;
    if (left < right)
    {
        mid = (left + right) / 2;
        partition(left, mid);
        partition(mid + 1, right);
        merge(left, right);
    }
}

int main()
{
    int N;
    cin >> N;
    sorted = new int[N];

    for (int i = 0; i < N; i++)
        scanf("%d", &arr[i]);

    partition(0, N - 1);

    for (int i = 0; i < N; i++)
        cout << arr[i] << '\n';
}

먼저 문제가 발생하는 원인을 생각해 보았다.
N개의 공간 10000000개를 모두 저장하면 공간 복잡도에 문제가 생기는 것 같다. (제한된 메모리는 8MB이다.)
그렇다면, 10000000개를 모두 저장하지 않고, 숫자를 정렬할 방법이 필요하다.
또한 주목할 점은, 이 전 문제에서 입력의 조건은 '중복되지 않는다'였다.
하지만, 이번 문제는 그러한 조건이 없다.

정리해서 이야기 해보면
1. 숫자는 0~10000사이의 자연수이다.
2. 입력의 숫자는 중복될 수 있다.
3. 메모리는 8MB의 제한이 있다. 즉, 10000000개를 모두 저장하는 메모리, 10^7 * 4byte를 하면 '40MB', 메모리를 초과한다.
그렇다면, 10001개의 공간을 만들고, 공간 내의 숫자를 증가 시키면서 count하면 메모리를 절약 할 수 있을 것이다.

이 방법으로 문제를 해결할 시, C로는 문제가 없지만, C++로 해결하려면 문제가 발생한다.

 

[C 코드]

#include <stdio.h>
#define Max 10001

int main()
{

    int N;
    scanf("%d", &N);

    int input[Max] = {0};

    for (int i = 0; i < N; i++)
    {
        int tmp;
        scanf("%d", &tmp);
        input[tmp] += 1;
    }

    for (int i = 1; i < Max; i++)
    {
        for (int j = 0; j < input[i]; j++)
        {
            printf("%d\n", i);
        }
    }
}

먼저 해결책을 살펴보면
C++로 알고리즘을 풀 때 자주 사용한다는 방법은 다음과 같다.

ios_base::sync_with_stdio(false);
cin.tie(null);
cout.tie(null);

문단의 각 내용을 살펴보면,
1. ios_base::sync_with_stdio
C의 stdio(;Standard input output)과 C++의 iostream(input output stream)을 동기화 시켜주는 역할을 한다.
즉, 이러한 동기화를 통해, C의 버퍼를 포기하고, C++만의 독립적인 버퍼를 사용함으로써, 사용 버퍼 수의 감소를 통한 실행 시간 상승을 꾀할 수 있는 것이다.
2. 이러한 과정에서 cin과 cout의 동기화를 해제한다.

이 문단을 cpp의 앞에 삽입한다면, 문제를 해결할 수 있다.

 

[해결한 코드]

#include <iostream>
#define Max 10001

using namespace std;

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

    int N;
    cin >> N;

    int input[Max] = {0};

    for (int i = 0; i < N; i++)
    {
        int in;
        cin >> in;
        input[in] += 1;
    }

    for (int i = 1; i < Max; i++)
    {
        for (int j = 0; j < input[i]; j++)
        {
            cout << i << '\n';
        }
    }
}

 

 

참조

https://tooo1.tistory.com/72

[백준(BOJ)] 10989번 : 수 정렬하기 3 - C++[CPP]