๋จ๊ท๋ ํต๋๋ฌด๋ฅผ ์ธ์ ๋๊ณ ๊ฑด๋๋ฐ๊ธฐ๋ฅผ ์ข์ํ๋ค. ๊ทธ๋์ 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,n), (2,n-1), ... ๋ฒ๊ฐ์๊ฐ๋ฉด์ ๋ฃ์ด์ ์๋ก์ด ๋ฐฐ์ด์ ๋ง๋ฆ
๐ก ์๋ก ๋ง๋ ๋ฐฐ์ด์ ์ธ์ ํ ์ซ์ ์ฐจ์ด๋ฅผ ๋น๊ตํ์ฌ ์ ์ผ ํฐ ์ซ์๋ฅผ ์ถ๋ ฅํจ
1) ์ซ์์ด์ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํจ
Arrays.sort(arr);
2) ์์ ์ซ์๋ถํฐ ํ๋์ฉ (1,n), (2,n-1), ... ๋ฒ๊ฐ์๊ฐ๋ฉด์ ๋ฃ์ด์ ์๋ก์ด ๋ฐฐ์ด์ ๋ง๋ฆ
for(int i=0, j=0; j<n/2; i=i+2, j++) {
wood[j] = arr[i];
wood[n-j-1] = arr[i+1];
}
if(n % 2 == 1)
wood[n/2] = arr[n-1];
3) ์๋ก ๋ง๋ ๋ฐฐ์ด์ ์ธ์ ํ ์ซ์ ์ฐจ์ด๋ฅผ ๋น๊ตํ์ฌ ์ ์ผ ํฐ ์ซ์๋ฅผ ์ถ๋ ฅํจ
int max = Math.abs(wood[0]-wood[n-1]);
for(int i=1; i<n; i++)
max = Math.max(max,Math.abs(wood[i]-wood[i-1]));
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Greedy_13 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int tc = Integer.parseInt(br.readLine());
while(tc-- > 0) {
int n = Integer.parseInt(br.readLine());
int arr[] = new int[n];
int wood[] = new int[n];
String s[] = br.readLine().split(" ");
for(int i=0; i<n; i++)
arr[i] = Integer.parseInt(s[i]);
Arrays.sort(arr);
for(int i=0, j=0; j<n/2; i=i+2, j++) {
wood[j] = arr[i];
wood[n-j-1] = arr[i+1];
}
if(n % 2 == 1)
wood[n/2] = arr[n-1];
int max = Math.abs(wood[0]-wood[n-1]);
for(int i=1; i<n; i++)
max = Math.max(max,Math.abs(wood[i]-wood[i-1]));
System.out.println(max);
}
}
}
์ฑ๊ณตโจ
(๊ฐ์ฅ ๋ ๊ฐ๊ณผ ์ฒ์ ๊ฐ์ด ์ธ์ ํ๋ ๊ฒ์ ๋ฐ๋์ ๊ณ ๋ คํด์ค์ผ ํ๋ค!)