[알고리즘] 통나무 건너뛰기

구현 방식

• 맨 처음과 끝도 차이가 별로 없어야 하므로,
• 오름차순이었다가 ~ 정점 찍고 내림차순 모양으로 통나무를 정렬해야한다.
• 그러면 통나무를 먼저 오름차순으로 정렬하고, 다른 배열에 양쪽 가장 자리에서부터 안쪽으로 숫자를 채워나면서 만들자.

코드

• 최종 코드는 아래와 같다.

#include <bits/stdc++.h>

using namespace std;


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

	int T, N, h;
	cin >> T;
	while (T--)
	{
		cin >> N;
		priority_queue<int> pq;
		for (int i = 0; i < N; i++)
		{
			int h;
			cin >> h;
			pq.push(h);
		}
		solution(N, pq);
	}

	return 0;
}

void solution(int N, priority_queue<int>& pq)
{
	vector<int> order(N);
	int h;
	for (int i = 0, j = N - 1; !pq.empty(); i++, j--)
	{
		// 왼쪽 채우기
		if (!pq.empty())
		{
			h = pq.top();
			pq.pop();
			order[i] = h;
		}
		// 오른쪽 채우기
		if (!pq.empty())
		{
			h = pq.top();
			pq.pop();
			order[j] = h;
		}
	}

	int diff, result = abs(order[0] - order[N - 1]);
	for (int i = 1; i < N; i++)
	{
		diff = abs(order[i-1] - order[i]);
		result = max(diff, result);
	}

	cout << result << "\n";

}