[BOJ/C++] 백준 2751번: 수 정렬하기 2

 

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

 

 

🧨 시간 초과!

 

처음은 퀵 정렬로 구현하였으나 시간 초과로 실패했다. 

두 번째엔 힙 정렬로 바꾸었지만 시간 초과! 

 

#1

힙 정렬을 구현하였을 때, 시간초과의 원인은 출력방식에 있었다.

cout << n << endl;

endl을 "\n"로 바꾸니 힙 정렬 구현 코드의 수정 없이도 바로 통과되었다.

(무거운 flush 연산과 관련된 이야기인데, 조만간 따로 정리해 볼 예정이다.)

 

#2

설마! 처음에 구현했던 퀵 정렬도 혹시...? 하는 마음에 endl을 "\n"로 바꾸어 시도해 보았지만 여전히 시간초과다.🤣

나의 퀵 정렬 구현 코드를 다시 살펴보니, 피벗(pivot)을 랜덤 선택하는 과정을 넣지 않아, 최악의 pivot이 선택되는 듯 하였다. 

이후 랜덤하게 선택하도록 코드를 수정해주었더니 통과하였다. 😀

퀵 정렬에서 pivot 랜덤 선택은 일반적으로 좋은 평균 성능을 제공한다!

 

최악의 시간 복잡도를 피해라!

 

 

 

---

 

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

 

 

 

 

 

입출력 예시

입출력 예시

 

입출력 예시

 

 

 

---

 

풀이 #1 | 힙 정렬(Heap Sort)

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

/* 배열을 (최대)힙 구조로 변환하는 함수 (재귀적) */
void heapify(vector<int>& vec, int n, int i) {
    int largest = i;        // 루트를 가장 큰 값으로 초기화
    int left = 2 * i + 1;   // 왼쪽 자식 노드
    int right = 2 * i + 2;  // 오른쪽 자식 노드

    /* 왼쪽 자식이 루트보다 큰 경우 */
    if (left < n && vec[left] > vec[largest])
        largest = left;

    /* 오른쪽 자식이 현재 가장 큰 값보다 큰 경우 */
    if (right < n && vec[right] > vec[largest])
        largest = right;

    /* 가장 큰 값이 루트가 아닌 경우 */
    if (largest != i) {
        swap(vec[i], vec[largest]);
        
        heapify(vec, n, largest);
    }
}

/* 힙에서 최대 값을 제거하며 벡터를 정렬하는 함수(힙 정렬) */
void heapSort(vector<int>& vec) {
    int n = vec.size();

    for (int i = n / 2 - 1; i >= 0; --i)
        heapify(vec, n, i);

    /* 힙에서 요소를 추출하여 정렬 */
    for (int i = n - 1; i >= 0; --i) {
        swap(vec[0], vec[i]);
        heapify(vec, i, 0);
    }
}

int main() {
    int N;
    cin >> N;

    vector<int> nums;
    for(int i = 0; i < N; ++i) {
        int num;
        cin >> num;

        nums.push_back(num);
    }

    /* 정렬 */
    heapSort(nums);

    for(int n : nums) {
        cout << n << "\n";
    }

    return 0;
}

 

 

 

풀이 #2 | 퀵 정렬(QuickSort)

• pivot을 꼭 랜덤으로 선택해야한다.
• 시드 값은 main() 함수가 실행되자마자 설정하도록 했다.

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;

/* 백터 요소 a와 b를 바꾸어주는 함수 */
void swap(int& a, int& b) {
    int tmp = a;
    a = b;
    b = tmp;
}

/* pivot을 기준으로 벡터를 분할하는 함수 */
int partition(vector<int>& vec, int low, int high) {
    /* pivot을 랜덤으로 선택하고 마지막 요소와 교체 */
    int randomPivotIdx = low + rand() % (high - low + 1);
    swap(vec[randomPivotIdx], vec[high]);
    
    int pivot = vec[high];
    int i = low - 1;

    for (int j = low; j <= high - 1; ++j) {
        if (vec[j] < pivot) {
            ++i;
            swap(vec[i], vec[j]);
        }
    }

    swap(vec[i + 1], vec[high]);
    return (i + 1);
}

/* 재귀적으로 분할과 정렬을 하는 함수 (퀵 정렬) */
void quickSort(vector<int>& vec, int low, int high) {
    if (low < high) {
        int pivot = partition(vec, low, high);

        quickSort(vec, low, pivot - 1);
        quickSort(vec, pivot + 1, high);
    }
}

int main() {
    srand(time(0));

    int N;
    cin >> N;

    vector<int> nums;
    for(int i = 0; i < N; ++i) {
        int num;
        cin >> num;

        nums.push_back(num);
    }

    quickSort(nums, 0, nums.size() - 1);

    for(int n : nums) {
        cout << n << "\n";
    }

    return 0;
}

 

 

---