✔️ 문제

남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 차가 최소가 되게 하려 한다.

통나무 건너뛰기의 난이도는 인접한 두 통나무 간의 높이의 차의 최댓값으로 결정된다. 높이가 {2, 4, 5, 7, 9}인 통나무들을 세우려 한다고 가정하자. 이를 [2, 9, 7, 4, 5]의 순서로 세웠다면, 가장 첫 통나무와 가장 마지막 통나무 역시 인접해 있다. 즉, 높이가 2인 것과 높이가 5인 것도 서로 인접해 있다. 배열 [2, 9, 7, 4, 5]의 난이도는 |2-9| = 7이다. 우리는 더 나은 배열 [2, 5, 9, 7, 4]를 만들 수 있으며 이 배열의 난이도는 |5-9| = 4이다. 이 배열보다 난이도가 낮은 배열은 만들 수 없으므로 이 배열이 남규가 찾는 답이 된다.

[입력]
입력은 T개의 테스트 케이스로 이루어져 있다. 첫 줄에 T가 주어진다.

이어지는 각 줄마다 첫 줄에 통나무의 개수를 나타내는 정수 N(5 ≤ N ≤ 10,000), 둘째 줄에 각 통나무의 높이를 나타내는 정수 Li가 주어진다. (1 ≤ Li ≤ 100,000)

[출력]
각 테스트 케이스마다 한 줄에 주어진 통나무들로 만들 수 있는 최소 난이도를 출력하시오.

😎 소스 코드

T = int(input())
answer = []

for _ in range(T):
	# get input
	N = int(input())
	L = list(map(int, input().split()))
	
	L.sort()

	# rearrange logs
	rearrange = [None] * N
	left = 0
	right = N-1

	for i in range(N):
		if i == 0 or i % 2 == 0:
			# index: 0 or even number 
			rearrange[left] = L[i]
			left += 1
		else:
			# index: odd number
			rearrange[right] = L[i]
			right -= 1
	
	# find maximum height
	max = 0
	for i in range(N-1):
		 if max < abs(rearrange[i] - rearrange[i+1]):
			 max = abs(rearrange[i] - rearrange[i+1])
	answer.append(max)

for num in range(T):
	print(answer[num])

✊ 문제를 풀고 나서

어제 저녁에 이 문제를 풀기 시작했다. 처음에 너무 쉽게 생각하고 간단하게 작성해서 제출했다가 어림도 없지.. 틀렸습니다 나와서 문제를 다시 생각해봤다. 침대에 누워서 고민하다가 아이디어가 떠올라서 러프하게 적어두고 잠에 들었다.

생각한 방법은, 입력받은 숫자들을 오름차순으로 정렬을 한다. 이렇게 정렬된 리스트(L.sort())를 바탕으로 통나무들의 위치(rearrange = [])를 재배치할 것이다. N만큼 for loop로 돌면서 인덱스가 0, 짝수이면 rearrange 리스트의 left 인덱스에 저장하고, 인덱스가 홀수이면 right인덱스에 저장한다. 따라서 가장 큰 숫자가 리스트의 정 가운데에 위치하게 된다.

이제 새롭게 재배치된 리스트에서 통나무의 최대 높이차를 구하면 된다. 절대값을 이용하여 max값을 찾아냈다. 그리고 출력하면 끝.

보기와는 다르게 좀 어려웠던 문제였다. 어쨌든 풀어서 뿌듯하다.