[백준] 11497번 - 통나문 건너뛰기(Java)(○)

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

11497번: 통나무 건너뛰기

 

<문제풀이>

1. 오름차순 정렬을 한다.

2. 가장 큰 기둥을 중간에 배치하고 그 다음 큰 기둥은 오른쪽에, 그 다음 큰 기둥은 왼쪽에 배치한다.

3. 이런 식으로 마지막까지 배치를 완료한다.
4. ArrayList A는 오른쪽에 배치하는 기둥을 넣고, ArrayList B는 왼쪽으로 배치하는 기둥을 넣도록 한다.

5. 가장 큰 수는 A와 B 모두 집어넣는다.

6. 그 다음 수부터 번갈아가면서 A, B에 집어 넣는다.
7. 삽입하면서 그 전의 값의 차이를 계속 최대값으로 업데이트 한다.
8. A와 B의 마지막 값들끼리의 차를 마지막으로 종료한다.

<코드구현>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Arrays;


public class Main {
    static int T, N;
    static int[] A;
    static ArrayList<Integer> listA, listB;

    void Solve() {
        int ans = -1, lastA = 0, lastB = 0;
        // 수를 번갈아 교차로 집어넣을 ArrayList 두벌을 준비
        listA = new ArrayList<>();
        listB = new ArrayList<>();
        Arrays.sort(A); // 오름차순 정렬
        // 가장 큰 수가 중간에 오도록 두 리스트에 모두 집어 넣는다.
        listA.add(A[N]);
        listB.add(A[N]);
        int num=0, cnt=0;
        for (int i=N-1; i>0; i--) {
            if (cnt == 0) {
                int a = listA.get(num) - A[i];
                ans = Math.max(ans, a);
                listA.add(A[i]);
                lastA = A[i];
                cnt++;
            } else {
                int b = listB.get(num) - A[i];
                ans = Math.max(ans, b);
                listB.add(A[i]);
                lastB = A[i];
                num++;
                cnt = 0;
            }
        }
        // 처음과 끝수의 차이도 업데이트
        int lastGap = Math.abs(lastA - lastB);
        ans = Math.max(ans, lastGap);
        System.out.println(ans);
    }
 
    public static void main(String[] args) throws Exception {
        Main m = new Main();
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        T = Integer.parseInt(st.nextToken());
        for (int i=0; i<T; i++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            A = new int[N+1];
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<N; j++) {
                A[j+1] = Integer.parseInt(st.nextToken());
            }
            m.Solve();
        }
    }
}