[BaekJoon 10989][🟤1] 수 정렬하기 3

❓ 문제

백준 10989 - “수 정렬하기 3”

🎯 난이도

Bronze 🟤1

🧠 풀이

1. 내 풀이 (정렬)

- 알고리즘

• Sorting

- 설명

입력받은 수를 카운팅 하는 방식으로 정렬하는 풀이이다.

처음에는 시간 제한 5초만 생각하고, 그냥 vector에 때려넣고 sort하면 끝 아닌가? 라고 생각했다.

하지만 메모리 제한 '8Mb'를 보고, 그렇게 간단하게는 할 수 없다는 걸 깨닫고 이 풀이를 생각해냈다.

메모리 제한 8Mb라는건, int 자료형을 썼을 때 200만개의 입력을 받을 수 있다는 뜻이고, 이는 1 ≤ N ≤ 10,000,000 조건에 비하면 한참 모자르다.

따라서 배열로 미리 10,000개의 인자를 받을 수 있게끔 만들고, 각 입력이 들어올 때마다 해당 배열의 숫자를 1씩 올리는 방식으로 정렬했다. 이렇게 하면 마지막에 각 배열의 숫자만큼 출력을 반복해주기만 하면 끝난다.

입력과 출력 모두 O(N) 시간 복잡도 이므로, 최종적으로 시간 복잡도가 O(N)이라고 볼 수 있다.

- 코드

내 풀이 코드

#include <iostream>


using namespace std;

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

    int iN{};
    cin >> iN;

    int arrNumber[10001]{};

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

        // 들어온 숫자 카운트
        ++arrNumber[iInput];
    }

    for(int i = 0; i <= 10000; ++i)
    {
        for(int j = 0; j < arrNumber[i]; ++j)
        {
            // 숫자마다 카운트 된 만큼 출력
            cout << i << "\n";
        }
    }

    return 0;
}

---

2. 추가 풀이 (출력 최적화)

- 알고리즘

• Sorting

- 설명

내 풀이에서 string을 이용한 출력 최적화를 하는 방식이다.

정렬은 나의 원래 풀이대로 하면 되지만, 모든 숫자를 반복문마다 계속해서 cout을 통해 출력하므로, N이 커지면 출력 오버헤드가 심해진다.

따라서 미리 capacity를 할당한 string에 출력을 더하고, 일정 size가 되기 전에 출력하고 다시 버퍼를 비워주는 식으로 출력하면, cout 자체의 '버퍼링'과 출력 연산자 (<<)의 호출 '오버헤드'를 상당히 줄일 수 있다.

이 방법도 출력 최적화만 한 것이지 알고리즘 자체는 바뀌지 않으므로 시간 복잡도는 여전히 O(N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <string>


using namespace std;

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

    int iN{};
    cin >> iN;

    int arrNumber[10001]{};

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

        // 들어온 숫자 카운트
        ++arrNumber[iInput];
    }

    // 1 << 20 은 대략 1Mb
    const size_t FLUSH_LIMIT = 1 << 20;

    string strOutput{};
    strOutput.reserve(FLUSH_LIMIT * 2);

    for(int i = 0; i <= 10000; ++i)
    {
        for(int j = 0; j < arrNumber[i]; ++j)
        {
            strOutput += to_string(i);
            strOutput += '\n';

            // FLUSH_LIMIT 넘기면 출력하고 버퍼 비우기 (재할당 방지, 출력 덩어리 크기 제한)
            if(strOutput.size() > FLUSH_LIMIT)
            {
                cout << strOutput;
                strOutput.clear();
            }
        }
    }

    cout << strOutput;

    return 0;
}

---

💭 후기

배운 점은 메모리 제한에 의한 알고리즘 선택과, 출력의 최적화이다.

이 문제처럼 테스트 케이스 수가 크고 메모리 제한이 빡빡한 경우는 이러한 카운팅 방식의 정렬을 사용하는 것이 좋다.

또한 출력이 너무 많은 경우는 string을 사용한 덩어리로 출력하는 방식을 사용하면 시간도 상당히 단축시킬 수 있다. 이를 비유하자면 다음과 같이 표현할 수 있다.

문 한 번 열때마다 택배 하나씩 배달 1000회 vs 문 한 번 열고 택배 1000개 한 번에 배달

당연히 후자가 빠르다. cout <<을 통한 출력은 생각보다 호출 오버헤드가 크다는 것을 꼭 기억하자.