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

 

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

 

---

 

문제

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

 

 

 

 

 

입출력 예시

입출력 예시

 

입출력 예시

 

 

 

---

 

풀이 #1 | 퀵 정렬 (Quick Sort) 구현

퀵 정렬(Quick Sort)을 구현한 풀이

#include <iostream>
#include <vector>
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) {
    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() {
    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 << endl;
    }
    
    return 0;
}

 

풀이 #2 | 내장함수 사용 (sort)

algorithm 내장함수인 sort()를 사용한 풀이

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

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

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

        nums.push_back(num);
    }

    /* algorithm 함수 사용해서 오름차순 정렬 */
    sort(nums.begin(), nums.end());

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

    return 0;
}

---