[BOJ 2750] 수 정렬하기 - [구현, 정렬]

[BOJ 2750] 수 정렬하기 - [구현, 정렬]

문제 링크

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

문제 요약

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. (N은 1,000 이하, 중복 없는 정수)

접근 방법

• 자료구조: std::vector<int> (동적 배열) 또는 크기 1000 이상의 정적 배열
• 알고리즘: 1. C++ STL의 std::sort() 함수를 사용하는 방법 ($O(N \log N)$) 2. 기초 정렬 알고리즘(버블, 선택, 삽입 정렬)을 직접 구현하는 방법 ($O(N^2)$)
• 핵심 아이디어: 데이터 개수가 1,000개로 적으므로 어떤 정렬 알고리즘을 사용해도 시간 제한(1초) 내에 해결 가능합니다. 가장 효율적이고 간결한 std::sort()를 사용합니다.

풀이 코드

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

using namespace std;

int main() {
    // 1. 입력 속도 최적화 (선택 사항)
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    // 2. n개의 정수를 저장할 벡터 선언 및 입력
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    // 3. 오름차순 정렬 (Intro Sort: Quick + Heap + Insertion)
    sort(v.begin(), v.end());

    // 4. 결과 출력
    for (int i = 0; i < n; i++) {
        cout << v[i] << "\n";
    }

    return 0;
}

시간/공간 복잡도

• 시간 복잡도: $O(N \log N)$ (std::sort 사용 시)
• 공간 복잡도: $O(N)$ (입력값 저장을 위한 벡터 공간)

실행 결과 (예상)

• 메모리: 약 2024 KB
• 시간: 약 0 ms ~ 4 ms

핵심 포인트

1. 정렬 알고리즘의 선택: $N \le 1,000$인 경우 $O(N^2)$도 가능하지만, 실무나 고난도 코딩 테스트에서는 항상 $O(N \log N)$인 std::sort를 우선적으로 고려해야 합니다.
2. 입출력 방식: 데이터 개수가 적을 때는 상관없지만, 많을 경우 endl보다는 \n을 사용하는 것이 속도 면에서 유리합니다.

예제 확인

• 예제 입력 1:
• 5 5 2 3 4 1
• 예제 출력 1:(입력된 5, 2, 3, 4, 1이 오름차순으로 정확히 정렬됨 확인)
• 1 2 3 4 5