백준16209 수열 섞기

작성일 | In

문제 링크

  • http://icpc.me/16209

사용 알고리즘

  • 그리디

시간복잡도

  • O(NlogN)

풀이

모든 숫자들이 0 이상이라면 내림차순으로 정렬을 한 뒤, deque의 앞/뒤에 번갈아가며 넣어주면 됩니다.
그러나 이 문제는 양수, 0, 음수가 모두 나옵니다.

0 이하인 수와 0 초과인 수로 분리한 뒤, 각각 절댓값이 큰 순서대로 정렬을 해줍니다.
그리고 각각을 서로 다른 deque의 앞/뒤에 번갈아가면서 넣어줍시다.

이제, 두 deque를 합쳐야 합니다.
두 deque를 합쳐지는 부분은 0 혹은 음수가 나오게 됩니다. 적절한 순서로 합쳐서 이 값의 절댓값을 최대한 작게 만들어주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;

vector<int> p, m;
deque<int> pp, mm;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	for(int i=0; i<n; i++){
		int t; cin >> t;
		if(t > 0) p.push_back(t);
		else m.push_back(t);
	}
	sort(all(p), greater<int>());
	sort(all(m));

	for(int i=0; i<p.size(); i++){
		if(i & 1) pp.push_back(p[i]);
		else pp.push_front(p[i]);
	}
	for(int i=0; i<m.size(); i++){
		if(i & 1) mm.push_back(m[i]);
		else mm.push_front(m[i]);
	}
	if(pp.size() && pp[0] > pp.back()) reverse(all(pp));
	if(mm.size() && mm[0] > mm.back()) reverse(all(mm));
	for(auto i : mm) cout << i << " ";
	for(auto i : pp) cout << i << " ";
}