11497번(통나무 건너뛰기)

첫 시도

• N이 10^4이므로 N^2 방식으로는 시도 x
• 처음에는 DP를 사용하여 해결방법을 탐색
• 생각해보니 각각 좌우 통나무의 높이 차이를 줄이는게 중요한 문제 -> 높이 순으로 정렬시킨다음 중앙부터 채워나간다면 해결되지 않을까?
• 각각 좌,우로 이동하는 left, right 변수를 만들고 한번씩 번갈아 가면서 남아있는 큰 숫자를 넣어줌
• 배열 정렬 + N개의 통나무 가운데부터 배치 + 난이도 계산 -> O(N)

해결

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

public class Main {

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

        int T = Integer.parseInt(br.readLine());
        for(int i = 0; i<T; i++){
            int N = Integer.parseInt(br.readLine());
            int[] input = new int[N];
            int max = 0;
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                input[j] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(input);
            int[] result = new int[N];
            int left = N/2-1;
            int right = N/2+1;

            result[N/2] = input[N-1];
            for(int j = N-2; j >= 0; j--){
                if(j % 2 == 0){
                    result[left--] = input[j];
                }
                else {
                    result[right++] = input[j];
                }
            }
            for (int j = 0; j < N-1; j++) {
                max = Math.max(max, Math.abs(result[j]-result[j+1]));
            }
            max = Math.max(max, Math.abs(result[0]-result[N-1]));
            System.out.println(max);
        }
    }
}

참고

• 직접구현