링크

11497 통나무 건너뛰기

문제

풀이

이 문제는 그리디 문제이다.
한참 고민하다가 풀이를 찾았다. 순서를 섞어서 인접한 두 통나무의 높이를 크게 하면 된다.
문제의 예시처럼 2 4 5 7 9가 있다고 한다면 2 5 9 7 4 가 되어야 |5-9| = 4로 답이 된다.

첫번째 2는 앞에서 채워넣고 두번째 4는 뒤에서 채워넣고 세번째 5는 앞에서 채워놓고 네번째 7은 뒤에서 채워넣고를 반복하고 하고 높이를 비교해서 최댓값을 뽑아내면 된다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int testCase = Integer.parseInt(br.readLine());
        for(int t=0;t<testCase;t++){
            int n = Integer.parseInt(br.readLine());

            List<Integer> list = new ArrayList<>();
            String[] arr = br.readLine().split(" ");

            for(int i=0;i<arr.length;i++){
                list.add(Integer.parseInt(arr[i]));
            }

            Collections.sort(list);

            Queue<Integer> queue = new LinkedList<>();

            //0 2 4 3 1
            //0 2 4 5 3 1
            for(int i=0;i<list.size();i+=2){
                queue.add(list.get(i));
            }

            if(n % 2 == 0){
                for(int i=list.size() - 1; i>0;i-=2){
                    queue.add(list.get(i));
                }
            } else{
                for(int i=list.size() - 2;i>0;i-=2){
                    queue.add(list.get(i));
                }
            }


            int[] answer = new int[queue.size()+1];
            for(int i=1;i<answer.length;i++){
                answer[i] = queue.poll();
            }

            answer[0] = answer[answer.length - 1];

            int max = 0;
            for(int i=1;i<answer.length-1;i++){
                max = Math.max(max, Math.max(Math.abs(answer[i] - answer[i-1]), Math.abs(answer[i] - answer[i+1])));
            }

            System.out.println(max);
        }

    }


}