[코딩테스트] SWEA 3503 초보자를 위한 점프대 설치하기(Java)

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
SWEA 3503 초보자를 위한 점프대 설치하기입니다.

포인트

해당 문제에서 구하라는 부분은 두 점프대의 높이차 중에서 가장 큰 값을 최소화하는 것입니다.

그래서 오름차순(내림차순)으로 정렬하면 차이가 적지 않나 라고 생각했지만, 점프대는 원형으로 설치하는 것이 문제입니다.

따라서 배열을 원형이라고 생각하여
배열의 0번의 왼쪽 인덱스는 N-1, 오른쪽 인덱스는 1로 생각하여 정렬된 기준으로 점프대의 높이를 설치합니다.

소스코드

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

public class Q3503 {
    private static int tc, N;
    private static Integer[] heights;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        tc = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        for (int t = 1; t <= tc; t++) {
            N = Integer.parseInt(br.readLine());
            heights = new Integer[N];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                heights[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(heights, Collections.reverseOrder());

            int idx = 0;
            int[] ans = new int[N];
            Arrays.fill(ans, -1);
            ans[idx] = heights[idx];
            idx++;
            for (int i = 1; i < N; i++) {
                int num = heights[i];
                if (ans[N - idx] == -1 && ans[idx] == -1) {
                    ans[N - idx] = num;
                } else if (ans[idx] == -1) {
                    ans[idx] = num;
                    idx++;
                }
            }

            int maxDiff = 0;
            for (int i = 0; i < N; i++) {
                int diff = Math.abs(ans[i] - ans[(i + 1) % N]);
                maxDiff = Math.max(maxDiff, diff);
            }
            sb.append("#").append(t).append(" ").append(maxDiff).append("\n");
        }
        System.out.println(sb);
    }
}

/*
3
7
13 10 12 11 10 11 12
5
2 4 5 7 9
8
6 6 6 6 6 6 6 6
 */

코드 설명

• Arrays.sort(heights, Collections.reverseOrder());
  프대 높이를 내림차순으로 정렬 (높은 점프대부터 배치하기 위해).

for (int i = 1; i < N; i++) {
    int num = heights[i];
    if (ans[N - idx] == -1 && ans[idx] == -1) {
        ans[N - idx] = num;
    } else if (ans[idx] == -1) {
        ans[idx] = num;
        idx++;
    }
}

• 두 번째 점프대부터는 idx를 기준으로 좌우 교차 배치합니다.(N-idx는 왼쪽 인덱스, idx는 오른쪽 인덱스)
• 이렇게 하면 큰 높이차가 발생할 수 있는 인접 점프대를 최대한 멀리 배치할 수 있습니다.

int maxDiff = 0;
for (int i = 0; i < N; i++) {
    int diff = Math.abs(ans[i] - ans[(i + 1) % N]);
    maxDiff = Math.max(maxDiff, diff);
}

• 원형 구조이므로 마지막과 첫 번째 점프대도 인접합니다.
• 인접한 점프대들 사이의 높이 차이를 모두 계산하고, 그 중 최댓값을 구합니다.