Description
n명의 축구 선수가 있다고 하자. 각 선수들은 왼쪽에서 오른쪽으로 1부터 n까지 번호가 매겨져 있고 각 선수 i는 실력 si를 가진다고 가정한다.
이 모든 선수를 두 팀으로 나누고자 하는데 각 팀에는 최소 한 명의 선수가 있어야 하며, 각 선수는 정확히 한 팀에 속해야 한다.
팀을 2개로 나눌 때의 기준은 첫 번째 팀의 가장 실력이 뛰어난 선수와 두 번째 팀의 가장 실력이 부족한 선수의 차이가 최대한 작도록 하여야 한다. 즉, 모든 선수들을 두 팀 A와 B로 나누었다고 하면 |max(A)−min(B)| 값이 최대한 작아지도록 하여야 한다. 여기서 max(A)는 팀 A 선수들 중의 최대 실력값이고, min(B)는 팀 B 선수들 중의 최소 실력값을 의미한다.
예를 들어, n=5이고 선수의 실력이 s=[3, 1, 2, 6, 4]이면, 가능한 팀 분할 방법 중 하나는 다음과 같다.
- 첫 번째 팀: A=[1, 2, 4]
- 두 번째 팀: B=[3, 6]
이 경우, |max(A)−min(B)| 값은 |4−3|=1이 된다.
이는 두 팀을 최적으로 분할하는 방법 중 하나를 의미하며 다른 분할 방법도 가능하다.
선수들에 대한 입력이 주어질 때 |max(A)−min(B)|의 최소값을 찾아 출력하는 프로그램을 작성하시오.
Input
첫 번째 줄에는 테스트 케이스의 개수인 정수 t(1 ≤ t ≤ 1000)가 주어진다. 그 후 t개의 테스트 케이스가 이어진다.
각 테스트 케이스는 두 줄로 구성되며 첫 번째 줄에는 선수의 수인 양의 정수 n(2≤n≤50)이 주어지고, 두 번째 줄에는 n개의 양의 정수 s1, s2, …, sn(1 ≤ si ≤ 1000)이 주어진다. 여기서 si는 i번째 선수의 실력이다. si의 값은 서로 다를 수 있다.
Output
각 테스트 케이스에 대해 |max(A)−min(B)|의 최소값인 정수를 한 줄에 하나씩 출력한다.
이 정수는 모든 선수를 두 팀으로 나누는 최적의 방법이다. 각 선수는 두 팀 중 정확히 한 팀에만 속해야 한다.
5
5
3 1 2 6 4
6
2 1 3 2 4 3
4
7 9 3 1
2
1 1000
3
100 150 200