[Problem Solving] BOJ 11497: 통나무 건너뛰기

문제 링크: https://www.acmicpc.net/problem/11497

 

통나무를 나열했을 때, 인접한 통나무 간 높이 차의 최댓값의 최솟값을 구하는 문제이다.

첫 번째 통나무와 마지막 통나무는 인접해 있기 때문에 오름차나 내림차로 정렬하면 인접한 통나무 간 높이 차의 최댓값이 매우 커진다. 

 

인접한 통나무 간 높이 차의 최댓값이 최소가 되는 경우는 가장 큰 통나무를 중심으로 하여, 큰 것 부터 작은 것 까지 가장 큰 통나무를 가운데 중심으로 하여 왼쪽, 오른쪽 번갈아 가면서 높은 경우이다.

 

이것을 구현하기 위해 deque 자료구조를 사용한 후, 높이 차의 최댓값을 구한다. 그것이 답이된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main 
{
    public static int T;
    public static int N;
    public static int[] L, D;
    public static int result;

    public static void input(BufferedReader br) throws IOException
    {
        N = Integer.parseInt(br.readLine());
        L = new int[N];
        String[] line = br.readLine().split(" ");
        for(int i = 0; i < N; i++)
        {
            L[i] = Integer.parseInt(line[i]);
        }
    }

    public static void solution()
    {
        result = 0;
        Arrays.sort(L);
        Deque<Integer> dq = new LinkedList<>();
        boolean flag = true;
        for(int i = N - 1; i >= 0; i--)
        {
            if(flag)
                dq.addLast(L[i]);
            else
                dq.addFirst(L[i]);
            flag = !flag;
        }
        L = new int[N];
        for(int i = 0; i < N; i++)
        {
            L[i] = dq.peekFirst();
            dq.removeFirst();
        }
        for(int i = 0; i < N; i++)
        {
            result = Math.max(result, Math.abs(L[i] - L[(i + 1) % N]));
        }
    }

    public static void output()
    {
        System.out.println(result);
    }

    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // Scanner sc = new Scanner(System.in);
        
        T = Integer.parseInt(br.readLine());
        for(int i = 0; i < T; i++)
        {
            input(br);
            // input(sc);
            solution();
            output();
        }
    }
}