[BOJ알고리즘, C++]#2470_두 용액, 정렬, 퀵 정렬, 투 포인터

#1. 문제

2470번: 두 용액

 

---

 

#2. 풀이

 

1. 퀵 정렬

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

 

[정의] : 퀵 정렬 알고리즘은 분할-정복 기반의 정렬 알고리즘입니다. 퀵 정렬은 피벗 원소를 기준으로 왼쪽은 이보다 작은 원소들, 오른쪽은 큰 원소들로 분할하는 작업을 더 이상 분할할 수 없는 크기까지 재귀적으로 수행하여, 최종적으로 하나의 정렬된 배열을 얻습니다. 

[성능] : 퀵 정렬 알고리즘의 평균 시간 복잡도는 O(n log n)으로, 이미 정렬된 상태이거나 역순으로 정렬된 상태에서 피벗 원소를 오른쪽 끝에 위치한 원소로 선택할 경우, O(n²) 시간 복잡도를 갖습니다. 이를 방지하기 위해, median-of-three 최적화를 활용할 수 있습니다.

 

2. 투 포인터

[알고리즘]#7_투 포인터

 

[정의] : 투 포인터 알고리즘은 두 개의 포인터를 활용해 원하는 조건을 만족하는 부분을 찾는 알고리즘입니다. 일반적으로, 투 포인터 알고리즘은 정렬된 배열에서 활용됩니다.

 

3. 정렬하고 투 포인터 알고리즘을 통해 조건을 만족하는 쌍을 찾는다!

1. 먼저, 주어진 배열에 대해 퀵 정렬을 수행합니다.
2. 그리고, 두 개의 포인터를 각각 배열의 첫 번째 위치와 마지막 위치로 초기화하고, 투 포인터 알고리즘을 수행하며 조건을 만족하는 쌍을 찾습니다!
3. 0에 가까우려면, 두 포인터가 가리키는 값의 합이 '양수'라면, 오른쪽 포인터를 왼쪽으로 한 칸 이동시키며, 음수라면, 왼쪽 포인터를 오른쪽으로 한 칸 이동시킵니다.

 

---

 

#3. 코드

 

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

typedef long long ll;

int N;
vector<ll> arr;

int MedianOfThree(vector<ll> &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<ll> &arr, int l, int r)
{
    int pivIdx = MedianOfThree(arr, l, r);
    swap(arr[pivIdx], arr[r]);

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

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

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

    return i + 1;
}

void QuickSort(vector<ll> &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 >> N;
    arr.resize(N);
    for (int i = 0; i < N; ++i)
    {
        cin >> arr[i];
    }

    // 퀵 정렬
    QuickSort(arr, 0, N - 1);

    // 투 포인터, 절대값이 가장 작은 수 찾기
    int left = 0;
    int right = N - 1;
    ll closeToZero = LLONG_MAX;

    pair<ll, ll> ans;

    while (left < right)
    {
        ll sum = arr[left] + arr[right];
        if (abs(sum) < abs(closeToZero))
        {
            closeToZero = sum;
            ans = make_pair(arr[left], arr[right]);
        }

        if (sum == 0)
        {
            break;
        }
        else if (sum > 0)
        {
            right--;
        }
        else if (sum < 0)
        {
            left++;
        }
    }

    cout << ans.first << ' ' << ans.second;

    return 0;
}

 

---