취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 16209번 문제인 수열 섞기이다.
문제는 아래 링크를 확인하자.

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

주어지는 정수의 부호가 모두 양수이면 문제의 답중 하나는 가장 큰 수를 중심에 두고 남은 수들을 큰 수부터 차례로 앞뒤로 번갈아 이어붙여 만든 순열이 됨을 직관적으로 알 수 있다. 주어지는 정수의 부호가 모두 음수인 경우 또한 유사한 성질이 있음을 쉽게 알 수 있다.

한편 양수와 음수가 곱해지면 구하는 값이 커지는 데에 아무런 보탬이 되지 않으므로 그러한 쌍을 최소화할 수 있다면 좋을 것이다. 위에서 만든 양수끼리의 순열과 음수끼리의 순열의 양 끝 값의 절댓값이 매우 작다는 점을 관찰하면 이러한 최소화를 간단히 해낼 수 있음을 관찰할 수 있다. 물론 0이 존재한다면 두 순열 사이에 0을 채워넣어 음의 값을 더할 일을 없애는 것이 최선일 것이다.

글쓴이는 위의 관찰을 바탕으로 정렬과 deque 등을 이용해 구현해 문제를 해결하였다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;

int N;
vector<int> vecL, vec0, vecR;
deque<int> dqL, dqR;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	while (N--) {
		int x; cin >> x;
		if (x < 0) vecL.emplace_back(-x);
		else if (x > 0) vecR.emplace_back(x);
		else vec0.emplace_back(x);
	}

	sort(vecL.begin(), vecL.end());
	sort(vecR.begin(), vecR.end());

	while (!vecL.empty()) {
		if (vecL.size() & 1) dqL.push_back(vecL.back());
		else dqL.push_front(vecL.back());
		
		vecL.pop_back();
	}

	while (!vecR.empty()) {
		if (vecR.size() & 1) dqR.push_front(vecR.back());
		else dqR.push_back(vecR.back());
		
		vecR.pop_back();
	}

	for (auto& x : dqL) cout << -x << ' ';
	for (auto& x : vec0) cout << x << ' ';
	for (auto& x : dqR) cout << x << ' ';
}