👨‍💻 문제

---

✍️ 풀이

산맥의 높이들이 주어지고, 가장 높은 산봉우리를 찾는 문제이다.

산봉우리의 조건은 아래와 같다.
hi <= ... <= hj >= ... >= hk

이 때 이 산봉우리의 높이는 이렇다.
Math.min((hj - hi), (hj - hk))

아래와 같이 산맥의 높이들이 주어진다면,
29 85 88 12 52 37 19 86 7 44

가장 높은 산봉우리의 높이는 67이다.
19 86 7

배열 축소

배열을 압축하면 봉우리 높이를 계산하기 쉬워진다.

상향 중인 선들과 하향 중인 선들을 하나의 직선으로 바꾼다.

리스트를 사용하여 입력과 동시에 압축을 진행하였다.

        StringTokenizer st = new StringTokenizer(br.readLine());
        
        while (st.hasMoreTokens()) {
            long value = Long.parseLong(st.nextToken());
            int i = arr.size();

            // 비었다면 삽입
            if (arr.isEmpty()) {
                arr.add(value);
                continue;
            }

            // 이전 값과 같은 값은 무조건 비허용
            if (arr.get(i-1) == value) {
                continue;
            }

            // 2번째 값은 1번째 값과 다르다면 무조건 삽입
            if (arr.size() == 1) {
                arr.add(value);
                continue;
            }

            // 상향 생략
            if (arr.get(i-2) < arr.get(i-1) && arr.get(i-1) < value) {
                arr.set(i-1, value);
                continue;
            }

            // 하향 생략
            if (arr.get(i-2) > arr.get(i-1) && arr.get(i-1) > value) {
                arr.set(i-1, value);
                continue;
            }

            // 방향 반전
            arr.add(value);
        }

결과값 산출

압축한 리스트를 돌며 가장 높은 봉우리를 찾아서 출력

        int N = arr.size();
        long maxHeight = 0;
        for (int i=1; i<N-1; i++) {
            long height = Math.min((arr.get(i) - arr.get(i-1)), (arr.get(i) - arr.get(i+1)));
            maxHeight = Math.max(maxHeight, height);
        }
        System.out.println(maxHeight);

---

📄 전체 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class _26031 {

    private static List<Long> arr = new ArrayList<>();

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

        while (st.hasMoreTokens()) {
            long value = Long.parseLong(st.nextToken());
            int i = arr.size();

            // 비었다면 삽입
            if (arr.isEmpty()) {
                arr.add(value);
                continue;
            }

            // 이전 값과 같은 값은 무조건 비허용
            if (arr.get(i-1) == value) {
                continue;
            }

            // 2번째 값은 1번째 값과 다르다면 무조건 삽입
            if (arr.size() == 1) {
                arr.add(value);
                continue;
            }

            // 상향 생략
            if (arr.get(i-2) < arr.get(i-1) && arr.get(i-1) < value) {
                arr.set(i-1, value);
                continue;
            }

            // 하향 생략
            if (arr.get(i-2) > arr.get(i-1) && arr.get(i-1) > value) {
                arr.set(i-1, value);
                continue;
            }

            // 방향 반전
            arr.add(value);
        }

        int N = arr.size();
        long maxHeight = 0;
        for (int i=1; i<N-1; i++) {
            long height = Math.min((arr.get(i) - arr.get(i-1)), (arr.get(i) - arr.get(i+1)));
            maxHeight = Math.max(maxHeight, height);
        }
        System.out.println(maxHeight);

    }

}