20.06.25 개발일지 - 수 정렬하기 3

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

10989번: 수 정렬하기 3

문제는 맞췄으나, 역시 혼자서는 맞추지를 못했습니다.

 

우선 어제 말한대로, 새로운 vector 선언을 최소화 한 Merge Sort를 구현하였습니다.

두 개의 subvector를 merge 할 때만 임시로 vector를 선언하였는데, 그럼에도 메모리가 부족하였습니다.

 

이 이상은 어떻게 줄일 방법이 없다고 판단하여 검색을 해보았습니다.

하지만 뜻밖에도, 문제는 다른 곳에 있었습니다.

 

대체로 다들 메모리와 시간 문제에 직면하는데,

다들 메모리 문제는 counting sort(입력값을 index로 하는 array에 갯수 저장)로 해결했습니다.

하지만 시간 문제는 알고리즘이 아니라 c스타일 array, c스타일 입출력.

그리고 입력의 최대값을 저장하여 출력 시 순회 횟수를 줄이는 것으로 시간을 줄였습니다.

 

대략적으로 시간복잡도를 계산하다보니 이런 부분은 신경쓰지 못한 것 같습니다.

다음에는 이런 부분까지도 항상 염두를 해두겠습니다.

 

#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    int size = 0, temp = 0, max = 0;
    int arr[10000] = { 0 };
    
    cin >> size;
    for (int i = 0; i < size; ++i)
    {
        scanf("%d", &temp);
        max = temp > max ? temp : max;
        ++arr[temp - 1];
    }

    for (int i = 0; i < max; ++i)
    {
        if (arr[i] > 0)
        {
            for (int j = 0; j < arr[i]; ++j)
            {
                printf("%d\n", i + 1);
            }
        }
    }

    return 0;
}