수열 섞기 (백준 16209)

안녕하세요. 오늘은 수열을 섞을 거예요.

문제

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

아이디어

일단 양수만 있다고 가정해봅시다.
곱이 최대가 되려면 큰것들은 모여있어야합니다.
그래서 작은것들을 순서대로 맨 왼쪽, 맨 오른쪽, 두번째로 왼쪽, 두번째로 오른쪽... 이런식으로 배치해주면 됩니다.
그런데 음수들만 있어도 마찬가지입니다. 음수들의 곱은 양수이므로 똑같이 해주면 됩니다. 이때는 절댓값을 기준으로 해야한다는 점을 유의해야합니다.

그러면 음수와 양수만 있다고 생각해봅시다.
음수와 양수 섞이지 않으면 곱은 양수입니다. 하지만 둘이 붙는 그 지점에서만 곱이 음수가 나옵니다. 이 값이 최소가 되려면 (음수들)(양수들)이 있을 때 음수들의 맨 오른쪽에 절댓값이 작은것, 양수들의 맨 왼쪽에 절댓값이 작은것을 두면 됩니다.

만약 0이 있으면 어떨까요? 그냥 (음수들)(0들)(양수들)순서대로 배치해주면 됩니다.

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;

vector <ll> make(vector <ll> v)
{
    ll N = v.size();
    vector <ll> ans(N);
    if (v.size() == 0) return ans;

    if (v[0] > 0) sort(v.begin(), v.end());
    else sort(v.begin(), v.end(), greater<>());

    for (ll i = 0; i < N - 1; i += 2)
    {
        ans[i / 2] = v[i];
        ans[N - i / 2 - 1] = v[i + 1];
    }
    if (N % 2 == 1) ans[N / 2] = v[N - 1];

    return ans;
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, i, x;
    vector <ll> plus, minus, zero;

    cin >> N;
    for (i = 1; i <= N; i++)
    {
        cin >> x;
        if (x < 0) minus.push_back(x);
        if (x == 0) zero.push_back(x);
        if (x > 0) plus.push_back(x);
    }
    minus = make(minus);
    plus = make(plus);

    ll size1 = minus.size(), size2 = plus.size(), size3 = zero.size();
    for (i = size1 - 1; i >= 0; i--) cout << minus[i] << ' ';
    for (i = 0; i < size3; i++) cout << zero[i] << ' ';
    for (i = 0; i < size2; i++) cout << plus[i] << ' ';
}

감사합니다.