[BOJ] 백준 [11497] 통나무 건너뛰기JAVA

https://www.acmicpc.net/problem/11497

11497번: 통나무 건너뛰기

문제

풀이

두 통나무 차이를 최소로 했을 때의 , 차이의 최대값을 구하면되는 문제이다.
난이도 차이가 크게 나지 않게하려면 우선 내림차순으로 정렬을 한 다음 양쪽으로 하나씩 넣어주면 된다.

양쪽으로 교차로 넣어줘야 하기때문에 Deque를 써서 addFirst와 addLast 메서드를 이용했다.
넣기전에 원래 있던 값과 새로 들어가야할 값 두개의 차이값이 최대값이면 갱신을 해주는식으로 하고
마지막에 다 채웠을 때 , 양쪽 끝 값을 비교하면 끝.

 

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        while(tc-->0){
            int n = Integer.parseInt(br.readLine());
            List<Integer> list = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).boxed().collect(Collectors.toList());
            ArrayDeque<Integer> dq = new ArrayDeque<>();
            list.sort(Collections.reverseOrder());
            dq.add(list.get(0));
            int max = 0;
 
            int index=1;
            while(dq.size()<n){
 
                int nextFront = list.get(index++);
                max = Math.max(max,dq.getFirst()-nextFront);
                dq.addFirst(nextFront);
 
                if(index<n) {
                    int nextLast = list.get(index++);
                    max = Math.max(max,dq.getLast()-nextLast);
                    dq.addLast(nextLast);
                }
            }
            max = Math.max(max,Math.abs(dq.getLast()-dq.getFirst()));
            System.out.println(max);
        }
    }
}