Codeforces 1419D1 Sage's Birthday (easy version)

문제

https://codeforces.com/problemset/problem/1419/D1

걸린 시간

00 : 41 : 28

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
using namespace std;

int n;
vector<int> a, reorder;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    a.resize(n); reorder.resize(n);
    for(auto& i : a) cin >> i;
    sort(a.begin(), a.end());
    int cnt = 0;
    for(int i = 1; i < n; i += 2){
        reorder[i] = a[cnt];
        cnt++;
    }
    for(int i = 0; i < n; i += 2){
        reorder[i] = a[cnt];
        cnt++;
    }
    if(n%2 == 0 && n > 1)
        cout << n/2-1 << "\n";
    else
        cout << n/2 << "\n";
    for(int i = 0; i < n; i++)
        cout << reorder[i] << " ";
    cout << "\n";
    return 0;
}

입력으로 받은 수를 차례로 정렬해서 작은 수 사이에 큰 수가 번갈아 놓이게끔 재정렬한다.

중복되는 수가 없으므로 결과값은 큰 수 사이에 놓은 작은 수의 개수가 정답이 된다. 수들이 모두 가장자리에 있는 2개 이하의 수일 경우도 처리해주어야 한다.