[백준 10989번] 수 정렬하기 3

문제 주소는 여기로

 

기본 알고리즘 공부 겸 숫자 정렬 문제를 풀어보고 있었습니다.

위 문제에 대해 제가작성한 답은 아래와 같습니다:

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void arraysort(vector<int>& array, int length)
{
     for (int i = 0; i < length; i++)
    {
        for (int j = i + 1; j < length; j++)
        {
            if (array[i] > array[j])
                swap(array[i], array[j]);
        }
    }
}

int main()
{
    int size;
    cin >> size;
    if (size < 1 || size > 10000000)
        return 1;

    vector<int> array(size);

    for (int i = 0; i < size; i++)
    {
        cin >> array[i];
        if (array[i] > 10000)
            return 1;
    }

    arraysort(array, size);

    for (int i = 0; i < size; i++)
        cout << array[i] << '\n';

    return 0;
}

간단한 selection sort를 이용한 문제풀이 방법입니다.

실제로 돌려보시면 잘 동작합니다.

2020.05.08 추가: 이 풀이는 2750. 수 정렬하기 문제의 답이었더라구요 ㅎㅎ 바로 제출해서 정답 판정 받았습니다.

 

그런데 문제는 백준 채점서버에서는 계속 '메모리 초과' 로 오답 처리가 되고 있네요.

메모리 제한은 8MB라고 하는데, 이를 코드 작성 중 및 테스트 할 때 어떻게 확인해 볼 수 있을지 궁금합니다.

 

이에 대해 답변을 다음과 같이 찾았습니다.

"모든 입력을 배열에 저장하면 당연히 메모리 초과가 발생한다."

라는 힌트를 얻을 수 있는데,

입력을 배열에 저장하지 않고 정렬할 수 있는 알고리즘엔 무엇이 있을까요?

 

counting sort, 한국어로는 계수 정렬이라고 하는 알고리즘이 있다고 합니다.

저는 배웠는데 까먹은건지, 처음 보는 건지 기억에는 없네요... ㅋㅋ

 

Counting sort는 O(n) 의 상당히 빠른 시간복잡도를 가진다고 합니다.

간단하게 말해서, 각 원소가 몇 번씩 등장하는지 세어 기록합니다.

이후 각 원소별로 세었던 순서만큼을 출력하는 것이죠.

더 자세한 설명은 이곳을 참고해 주세요.

 

그리하여 제가 새로 작성한 코드는 아래와 같습니다:

#include <iostream>
using namespace std;

#define ARRAY_SIZE 10000
int array[ARRAY_SIZE] = { 0, };
int main()
{
	ios_base::sync_with_stdio(false);

	int trial, input, maximum = 0;
	cin >> trial;

	

	for (int i = 0; i < trial; i++)
	{
		cin >> input;	
		array[input]++;
		if (input > maximum)
			maximum = input;
	}

	for (int i = 0; i <= maximum; i++)
	{
		while(array[i])
		{
			cout << i << '\n';
			array[i]--;
		}
	}

	return 0;
}

상당히 짧고 간단하죠?

10000개의 크기를 가진 배열을 먼저 만들고 (각 원소의 최댓값이 10000이므로),

모든 배열의 내용을 0으로 초기화한 후에,

한번 숫자를 입력받을 때마다 해당 배열의 값을 1 증가시킨 후,

배열의 값만큼 해당 원소의 인덱스값을 출력하는 코드예요.

 

이렇게 보면 정말 간단한데

저는 막 2차원 배열, 동적 벡터 등등으로 접근했다가 엄청 고생했네요 ㅠㅠ

이렇게 한 문제 계속 틀린 적도 처음 같아요... ㅋㅋ

그래두 이렇게 시도하면서 배우는 과정이 즐겁네요

 

덕분에 늘게 된 vector STL에 대한 지식...