[BOJ 2751] 수 정렬하기 2 - [정렬]

[BOJ 2751] 수 정렬하기 2 - [정렬]

문제 링크

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

문제 요약

• $N$개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
• 수의 개수 $N$은 최대 1,000,000개이며, 각 수는 중복되지 않는다.

접근 방법

• 자료구조: std::vector<int> (동적 배열)
• 알고리즘: $O(N \log N)$의 성능을 보장하는 정렬 알고리즘 (std::sort)
• 핵심 아이디어:
  • 데이터가 100만 개이므로 $O(N^2)$ 알고리즘(버블, 선택, 삽입 정렬)은 시간 초과가 발생한다.
  • C++의 std::sort는 최악의 경우에도 $O(N \log N)$을 보장하는 Intro Sort를 사용하여 이 문제에 적합하다.
  • 대량의 데이터를 출력해야 하므로 endl 대신 \n을 사용하고, 입출력 속도 향상을 위한 최적화 코드를 추가한다.

풀이 코드

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

using namespace std;

int main() {
    // 입출력 속도 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    // N개의 숫자를 담을 벡터 선언 및 입력
    vector<int> numbers(N);
    for (int i = 0; i < N; i++) {
        cin >> numbers[i];
    }

    // 오름차순 정렬 (Intro Sort: O(N log N))
    sort(numbers.begin(), numbers.end());

    // 결과 출력 (\n 사용으로 속도 확보)
    for (int i = 0; i < N; i++) {
        cout << numbers[i] << "\n";
    }

    return 0;
}

시간/공간 복잡도

• 시간 복잡도: $O(N \log N)$ (정렬 알고리즘 성능에 기인)
• 공간 복잡도: $O(N)$ (입력값 저장을 위한 벡터 크기)

실행 결과 (예상)

• 메모리: 약 12,000 KB (1,000,000 * 4 bytes + 벡터 오버헤드)
• 시간: 약 300 ~ 600 ms (정렬 및 출력 속도에 따라 변동)

핵심 포인트

1. 정렬 알고리즘 선택: 시간 제한(2초) 내에 100만 개의 데이터를 처리하기 위해 효율적인 정렬(Merge, Quick, Heap) 기반의 std::sort를 사용해야 한다.
2. 출력 속도: endl은 버퍼를 매번 비우기 때문에 매우 느리다. 대량 출력 시에는 반드시 \n을 사용해야 한다.
3. 입출력 동기화 해제: sync_with_stdio(false)를 통해 C++ 스트림의 성능을 극대화한다.

예제 확인

• 예제 입력 1:
• 5 5 4 3 2 1
• 예제 출력 1:
• 1 2 3 4 5