[BOJ알고리즘, C++]#11656_접미사 배열, 정렬, 퀵 정렬, 병합 정렬

 

#1. 문제

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

11656번: 접미사 배열

 

---

 

#2. 풀이

 

1. 병합 정렬

[알고리즘]#3_정렬 알고리즘

 

[정의] : 병합 정렬 알고리즘은 분할-정복 알고리즘을 기반으로, 주어진 배열을 두 부분 배열로 나누어 재귀적으로 정렬을 수행한 후, 최종적으로 두 부분 배열을 병합하여 하나의 정렬된 배열을 얻는 정렬 알고리즘입니다.

[성능] : 병합 정렬 알고리즘은 최악의 경우 O(n log n)의 시간 복잡도를 가지며, 비교적 효율적인 정렬 알고리즘입니다. 다만, 하나의 배열을 두 부분 배열로 정렬하여 분할할 때 추가적인 메모리 공간이 필요합니다. 

 

2. 퀵 정렬

[알고리즘]#3_정렬 알고리즘

 

[정의] : 퀵 정렬은 분할 정복 알고리즘에 기반한 정렬 알고리즘입니다. 퀵 정렬은 피벗 원소를 선택해, 이보다 작은 원소들은 왼쪽으로, 큰 원소들은 오른쪽으로 분할하고, 이렇게 나누어진 두 부분 배열에 대해 재귀적으로 정렬 작업을 수행하며 최종적으로 하나의 정렬된 배열을 얻습니다.

[성능] : 퀵 정렬 알고리즘은 최악의 경우 O(n²)의 시간 복잡도를 갖습니다. 이를 방지하기 위해, 퀵 정렬 알고리즘에서 피벗 원소의 선택 기준을 중간 값으로 설정하는 median-of-three 최적화 기술을 활용할 수 있습니다. 결과적으로, 퀵 정렬 알고리즘의 성능을 평균 시간 복잡도, O(n log n)으로 유지할 수 있게 됩니다.

 

3. 문자열 < 문자열, 사전순으로 정렬!

1. 병합 정렬 or 퀵 정렬을 수행합니다.
2. 정렬 기준은 사 전수로, operator >를 활용하면 사전순으로 먼저 나오는 문자열이 더 앞에 위치하게 됩니다.

 

---

 

#3. 코드

 

1. 병합 정렬

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

string S;

void Merge(vector<string> &str, int l, int m, int r)
{
    int leftSize = m - l + 1;
    int rightSize = r - m;

    vector<string> left(leftSize);
    vector<string> right(rightSize);

    for (int i = 0; i < leftSize; ++i)
        left[i] = str[l + i];

    for (int i = 0; i < rightSize; ++i)
        right[i] = str[m + 1 + i];

    int leftIdx = 0;
    int rightIdx = 0;
    int resIdx = l;

    while (leftIdx < leftSize && rightIdx < rightSize)
    {
        if (left[leftIdx] <= right[rightIdx])
        {
            str[resIdx++] = left[leftIdx++];
        }
        else
        {
            str[resIdx++] = right[rightIdx++];
        }
    }

    while (leftIdx < leftSize)
    {
        str[resIdx++] = left[leftIdx++];
    }

    while (rightIdx < rightSize)
    {
        str[resIdx++] = right[rightIdx++];
    }
}

void MergeSort(vector<string> &str, int l, int r)
{
    if (l < r)
    {
        int m = l + (r - l) / 2;

        MergeSort(str, l, m);
        MergeSort(str, m + 1, r);

        Merge(str, l, m, r);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> S;

    vector<string> arr;

    for (int i = 0; i < S.length(); ++i)
        arr.push_back(S.substr(i, S.length() - i));

    MergeSort(arr, 0, S.length() - 1);

    for (int i = 0; i < S.length(); ++i)
        cout << arr[i] << '\n';

    return 0;
}

 

2. 퀵 정렬

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

string S;

int MedianOfThree(vector<string> &arr, int l, int r)
{
    int m = l + (r - l) / 2;

    if (arr[l] > arr[m])
    {
        swap(arr[l], arr[m]);
    }
    if (arr[l] > arr[r])
    {
        swap(arr[l], arr[r]);
    }
    if (arr[m] > arr[r])
    {
        swap(arr[m], arr[r]);
    }

    return m;
}

int Partition(vector<string> &arr, int l, int r)
{
    int pivIdx = MedianOfThree(arr, l, r);
    swap(arr[pivIdx], arr[r]);

    string piv = arr[r];
    int i = l - 1;

    for (int j = l; j < r; ++j)
    {
        if (arr[j] <= piv)
        {
            i++;
            swap(arr[j], arr[i]);
        }
    }

    swap(arr[i + 1], arr[r]);

    return i + 1;
}

void QuickSort(vector<string> &arr, int l, int r)
{
    if (l < r)
    {
        int piv = Partition(arr, l, r);

        QuickSort(arr, l, piv - 1);
        QuickSort(arr, piv + 1, r);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> S;

    vector<string> arr;

    for (int i = 0; i < S.length(); ++i)
        arr.push_back(S.substr(i, S.length() - i));

    QuickSort(arr, 0, S.length() - 1);

    for (int i = 0; i < S.length(); ++i)
        cout << arr[i] << '\n';

    return 0;
}

 

---