3503. 초보자를 위한 점프대 배치하기

3503. 초보자를 위한 점프대 배치하기

로직은 우선 점프대를 오름차순으로 정렬한다.

그리고 가장 낮은 점프대(0번째)를 가운데에 넣고, 양 옆으로 번갈아 가면서 오름차순의 점프대를 넣어주면 된다.

양옆으로 넣어줘야 하기 때문에 deque 를 사용해서 문제를 풀었다.

이렇게 푼 이유는

만약 점프대가 오름차순으로 있다면, 원형이기 때문에 결국 가장 큰 점프대와 가장 낮은 점프대의 차이가 답으로 나올 것이다.

하지만 가장 낮은값을 가운데에 넣고, 그 앞뒤로 순차적으로 삽입을 하면, 평균적인 차이가 가장 낮게 나올 것이다.

<정답 코드>

#include<iostream>
#include<deque>
#include<vector>
#include<algorithm>
using namespace std;
 
int main()
{
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        int n;
        cin >> n;
        vector<int> v(n);
        deque<int> dq;
        for (int i = 0; i < n; i++)
        {
            cin >> v[i];
        }
 
        sort(v.begin(), v.end());
 
        for (int i = 0; i < n; i++)
        {
            if (i == 0)
            {
                dq.push_front(v[i]);
            }
            else
            {
                if (i % 2 == 1)
                {
                    dq.push_front(v[i]);
                }
                else
                {
                    dq.push_back(v[i]);
                }
            }
        }
 
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            if (i == n - 1)
            {
                ans = ans < abs(dq[i] - dq[0]) ? abs(dq[i] - dq[0]) : ans;
                continue;
            }
            else
            {
                ans = ans < abs(dq[i] - dq[i + 1]) ? abs(dq[i] - dq[i + 1]) : ans;
            }
        }
 
 
        cout << ans << "\n";
    }
 
    return 0;
}