문제
남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 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)
출력
각 테스트 케이스마다 한 줄에 주어진 통나무들로 만들 수 있는 최소 난이도를 출력하시오.
1
2
3
4
5
6
7
8
9
T = int(input())
for _ in range(T):
N = int(input())
S = list(map(int,input().split()))
S.sort()
maxv=0
for i in range(N-2):
maxv = max(maxv,abs(S[i]-S[i+2]))
print(maxv)
가장 인접한 수끼리 놓아야 차가 작게 나온다.
그렇다고 오름차순으로 두면 안되는게 처음이랑 마지막은 이어져있어서. 이 둘을 인접하게 두면 안된다.
따라서 최댓값을 중앙에 두고, 그 다음으로 큰 두 수를 최댓값의 양 옆 (두 수중 작은게 왼쪽, 큰게 오른쪽)으로 두는 행위를 반복해서 나온 수열을 대상으로 난이도를 계산해야 한다.
계산할 때는, 반복문을 돌면서 인접한 두 수의 차를 구해서 max를 갱신해주면 된다.
물론 원리는 위와 같지만, 실제로 수열을 만들어 줄 필요는 없다.
어차피 수열을 만들고 나면, 각 숫자가 자신과 가장 인접한 두 수를 양 옆에 두게 되게 때문이다.
그리고, 문제에서 나와있듯이 난이도는 최댓값으로 정해지기 때문에, 인접한 두 수중에서도 큰 수와의 차를 구하면 된다.
즉, 오름차순이 된 상태에서 자신보다 +2인 인덱스와의 차를 구해서 max를 갱신해나가면 된다.
(반복문의 range가 n-2인 이유는 +2인 인덱스와의 차를 구하는 것이기 때문에 저기까지만 해도 구하려는 경우의 수가 다 구해지기 때문이다.)