[BaekJoon 2751][⚪5] 수 정렬하기 2

❓ 문제

백준 2751 - “수 정렬하기 2”

🎯 난이도

Silver ⚪5

🧠 풀이

1. 내 풀이 (정렬)

- 알고리즘

• Sorting

- 설명

간단하게 sort를 이용한 정렬만 하면 되는 풀이이다.

이 문제는 정말 간단히 vector에 입력된 숫자들을 넣고, 정렬만 하면 되는 문제였다. 시간 제한이나 메모리 제한도 넉넉해서, 다른 컨테이너를 쓰는 것보다 vector를 사용해서 캐시 친화성도 챙기고, 미리 메모리 할당도 하는 식으로 이점만 챙겨가면서 입력 받으면 된다.

sort의 시간 복잡도가 곧 전체 시간 복잡도이므로, 이 풀이의 시간 복잡도는 O(N log N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>


using namespace std;

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

    int iN{};
    cin >> iN;

    vector<int> vecNumber{};
    vecNumber.reserve(iN);

    while(iN--)
    {
        int iInput{};
        cin >> iInput;

        vecNumber.push_back(iInput);
    }

    sort(vecNumber.begin(), vecNumber.end());

    // 한 문장에 최대로 나올 수 있는 문자 수는 -1000000\n : 9개이므로 여유 있게 10개라고 잡음
    const size_t iLimit{ static_cast<size_t>(iN) * 10 };

    string strOut{};
    strOut.reserve(iLimit);

    for(const int iOut : vecNumber)
    {
        strOut += to_string(iOut);
        strOut += '\n';
    }

    cout << strOut;

    return 0;
}

---

💭 후기

그냥 sort를 이용해서 정렬을 할 줄 아느냐를 물어보는 문제였다. 마지막에 출력 최적화를 위해 조금 트릭을 썼는데, 이는 전에 수 정렬하기 3에서 썼던 방식과 비슷하다.

하지만 저번에는 메모리 제한이 빡빡해서 1 << 20으로 대략 1Mb정도로 string의 공간을 할당하고, 재할당 전에 미리 clear 했던 것과는 다르게, 메모리가 넉넉하므로 최대로 나올 수 있는 string의 메모리 공간을 넉넉하게 미리 할당하고 한 번에 출력하는 방식으로 조금 변형했다. 앞으로도 자주 쓰일 트릭이니 꼭 기억해두자!