백준 11497 통나무 건너뛰기 C++

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

일반적인 정렬을 하면 첫 번째 원소와 마지막 원소를 비교했을 때 차이가 많이 나는 결과가 나오기 때문에 일반적인 정렬로는 해결할 수 없다.

 

정렬을 한 뒤 새로운 배열에 처음과 마지막 부분에 순서대로 삽입하는 방법을 생각해 볼 수 있다.

2, 4, 5, 7, 9 가 있으면 처음에 2, 마지막에 4, 다시 앞으로 와서 5, 다시 뒤로 가서 7, 다시 앞으로 와서 9 이런식으로 배열을 만들면 2, 5, 9, 7, 4 이렇게 만들어진다. 

 

하지만 이런식으로 만들려면 배열을 하나 더 만들어야 하기도 하고 구현하기도 번거롭다.

그래서 위의 배열 2개에서 찾은 규칙이 있는데, 그 규칙으로 간단하게 문제를 해결할 수 있다.

정렬된 배열을 순서대로 앞뒤에다 배치하기 때문에 정렬된 배열의 특정 원소에서 2칸 떨어진 원소가 새로 만든 배열에서는 바로 옆에 붙어있다는 것을 발견할 수 있다.

그렇기 때문에 정렬된 배열에서 2칸 떨어진 원소들을 비교하여 그 중 최댓값을 찾으면 된다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t, n;
	cin >> t;
	while (t--) {
		cin >> n;
		vector<int> v(n);
		for (int i = 0; i < n; i++) {
			cin >> v[i];
		}
		sort(v.begin(), v.end());
		int ans = 0;
		for (int i = 2; i < n; i++) {
			ans = max(ans, abs(v[i] - v[i - 2]));
		}
		cout << ans << "\n";
	}
};