백준 2750번 수 정렬하기 + 백준 2751번 수 정렬하기 2

문제 링크입니다: https://www.acmicpc.net/problem/2750

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

2750번은 c++ stl의 sort를 통해 구현해도 쉽게 통과가 됩니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

int N;

vector<int> v;

 

int main(void)

{

        cin >> N;

 

        for (int i = 0; i < N; i++)

        {

                 int num;

                 cin >> num;

                 v.push_back(num);

        }

 

        sort(v.begin(), v.end());

        for (int i = 0; i < N; i++)

                 cout << v[i] << endl;

 

        return 0;

}

 

반면, 2751번은 quickSort를 사용해도 시간초과가 발생합니다.

따라서 MergeSort를 통해 문제를 풀었습니다.

MergeSort는 최악의 경우에도 O(nlogn)인 반면에 quickSort는 평균적으로 O(nlogn)이지만 최악일 때는 O(n^2)이라 AC를 받지 못한 것 같습니다.

물론, 퀵정렬의 pivot을 제일 왼쪽에 있는 수로 하지 않고 3개를 골라 중간값을 pivot으로 이용한다면 성능개선이 되어 AC를 받을 수 있을 것 같습니다!

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 1000000;

 

int N;

int arr[MAX];

int tempArr[MAX];

 

/*

void partition(int low, int high, int &pivotpoint)

{

        int pivotItem = arr[low];

        int idx = low;

 

        for(int i=low + 1; i <= high; i++)

                 if (arr[i] < pivotItem) //pivotItem보다 arr[i]가 클 경우

                 {

                         idx++;

                         swap(arr[i], arr[idx]);

                 }

        pivotpoint = idx;

        swap(arr[low], arr[pivotpoint]); //정렬했을 때 위치해야하는 곳으로 이동

}

 

void quickSort(int low, int high)

{

        int pivotpoint;

 

        if (high > low)

        {

                 partition(low, high, pivotpoint);

                 quickSort(low, pivotpoint - 1);

                 quickSort(pivotpoint + 1, high);

        }

}

*/

 

/*

void quickSort(int low, int high)

{

        int pivot = low;

        int idx = low;

       

        if (high > low)

        {

                 for (int i = low + 1; i <= high; i++)

                         if (arr[i] < arr[pivot])

                         {

                                 idx++;

                                 swap(arr[idx], arr[i]);

                         }

 

                 swap(arr[low], arr[idx]);

                 pivot = idx;

 

                 quickSort(low, pivot - 1);

                 quickSort(pivot + 1, high);

        }

}

*/

 

void merge(int low, int mid, int high)

{

        int i = low, j = mid + 1, k = low;

 

        while (i <= mid && j <= high)

        {

                 if (arr[i] < arr[j])

                         tempArr[k] = arr[i++];

                 else

                         tempArr[k] = arr[j++];

                 k++;

        }

       

        if (i > mid)

                 for (int idx = j; idx <= high; idx++)

                         tempArr[k++] = arr[idx];

        else

                 for (int idx = i; idx <= mid; idx++)

                         tempArr[k++] = arr[idx];

 

        for (int idx = low; idx <= high; idx++)

                 arr[idx] = tempArr[idx];

}

 

void mergeSort(int low, int high)

{

        if (high>low)

        {

                 int mid = (low + high) / 2;

                 mergeSort(low, mid);

                 mergeSort(mid + 1, high);

                 merge(low, mid, high);

        }

}

 

int main(void)

{

        cin >> N;

 

        for (int i = 0; i < N; i++)

                 //cin >> arr[i];

                 scanf("%d", &arr[i]);

 

        //quickSort(0, N - 1);

        mergeSort(0, N - 1);

 

        for (int i = 0; i < N; i++)

                 //cout << arr[i] << endl;

                 printf("%d\n", arr[i]);

 

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~