BOJ - 수 정렬하기 3 10989

 

해결방법

원래는 sort를 사용하여 정렬을 해주면 되지 않을까 생각했는데, 메모리 제한과 시간제한을 보고 코드를 좀 변경했다.

입력되는 수는 10000보다 작은 자연수이므로, 배열을 10000정도 크기로 만들고, 입력받은 수를 배열의 인덱스로 사용하여 수가 입력될 때마다 값을 1 올려서 저장한다.

이후 출력할 때 입력받은 수의 값 만큼 출력을 반복해주면 된다.

 

정답 코드

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

using namespace std;

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

	int N;

	cin >> N;

    int input[10001] = { 0 };

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

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

	return 0;
}