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

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

 

가장 먼저 안 될 걸 알지만 그냥 vector에 입력을 쭉 받은 뒤 sort 함수를 사용해 정렬해 보았다

메모리 초과가 되었다...

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int sort(vector<int> &num, int add)
{
    int pnt = 0;
    vector<int> v = {};
    int mid = num.size() / 2;
    if (mid == 0)
        return (add > num[0]) ? 1 : 0;
    if (add > num[mid])
    {
        v.insert(v.begin(), num.begin() + mid, num.end());
        pnt += mid + sort(v, add);
    }
    else if (add < num[mid])
    {
        v.insert(v.begin(), num.begin(), num.end() - mid);
        pnt += sort(v, add);
    }
    else
    {
        pnt = mid;
    }
    return pnt;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, input;
    vector<int> num;
    int pnt = 0;

    cin >> n >> input;
    num.push_back(input);
    for (int i = 1; i < n; i++)
    {
        cin >> input;
        int pnt = sort(num, input);
        num.insert(num.begin() + pnt, input);
    }

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

다음은 매 입력 시마다 적정한 위치를 찾아서 넣을 수 있도록 구현하였는데 시간 초과가 떴다...

 

그런데 생각해 보니 굳이 저렇게 복잡하게 구현할 필요 없이 1부터 9까지의 숫자를 오름차순 정렬하는 거니까 총 1~9가 몇 번 나왔는지 체크해서 순서대로 출력하면 되지 않나 싶었다

#include <iostream>
#include <map>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    map<int, int> nums;
    int n, input;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> input;
        nums[input]++;
    }

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

그냥 map을 이용해 각 숫자들의 총 개수를 카운트한 뒤, 각 key를 value만큼 순서대로 출력했다