백준 2751번 [수 정렬하기 2](C++)-yes6686- 티스토리

백준 문제 풀이: 2751 [수 정렬하기 2]

---

문제 링크: https://www.acmicpc.net/problem/2751

문제 설명:

주어진 정수 n개의 수를 오름차순으로 정렬하는 문제입니다. 입력 범위가 크기 때문에 효율적인 알고리즘을 사용해야 합니다.

---

문제 해결 코드

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

// 퀵 정렬 함수
void quickSort(int* data, int start, int end) {
    if (start >= end) {
        return;
    }
    int key = start;
    int i = start + 1;
    int j = end;
    while (i <= j) {
        while (data[i] <= data[key] && i <= end) {
            i++;
        }
        while (data[j] >= data[key] && j > start) {
            j--;
        }
        if (i > j) {
            int temp = data[j];
            data[j] = data[key];
            data[key] = temp;
        }
        else {
            int temp = data[j];
            data[j] = data[i];
            data[i] = temp;
        }
    }
    quickSort(data, start, j - 1);
    quickSort(data, j + 1, end);
}

int arr[1000001];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    random_shuffle(arr, arr + n); // 랜덤 셔플을 통해 퀵 정렬의 성능 보장
    quickSort(arr, 0, n - 1); // 퀵 정렬 호출
    for (int i = 0; i < n; i++) {
        cout << arr[i] << '\n'; // 정렬된 결과 출력
    }
}

---

코드 설명

• 핵심 알고리즘: 퀵 정렬을 사용하여 데이터를 정렬합니다.
• 구현 세부사항:
  • 퀵 정렬의 효율성을 보장하기 위해 random_shuffle을 사용하여 배열을 섞습니다.
  • 분할 기준은 배열의 첫 번째 원소로 설정되며, 재귀적으로 왼쪽과 오른쪽 부분 배열을 정렬합니다.
  • 정렬 후 배열의 각 원소를 출력합니다.
• 시간 복잡도: 평균 O(n log n), 최악의 경우 O(n²)
• 공간 복잡도: O(log n) (재귀 호출 스택 사용)

---

결과

입력된 수를 오름차순으로 빠르게 정렬하여 출력합니다. 퀵 정렬의 특성과 random_shuffle의 조합으로 평균적으로 높은 성능을 보장합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!