LeetCode 1340. Jump Game V

문제

정수 배열 $arr$과 $1$ 이상의 정수 $d$가 주어진다.

인덱스 $i$에서 아래 조건을 만족시키면 인덱스 $j$로 점프할 수 있다.

• $arr[j] < arr[i]$
• $\max(i-d, 0) \le j \le \min(i+d, \texttt{arr.length})$
• $\min(i, j) < k < \max(i, j)$인 모든 $k$에 대해, $arr[k] < arr[i]$

풀이

인덱스 $i$로 점프할 수 있는 조건을 해석하면 다음과 같다.

• 인덱스 $i$의 양쪽으로, 거리 $d$ 이하의 $arr[i]$보다 큰 가장 가까운 원소

거리 조건만 빠지면, 스택을 응용하는 문제로 변한다.

즉, 점프를 통해 인덱스 $i$를 방문할 수 있는 곳은 좌우 각각 한 군데로 정해진다.

가장 가까운 원소가 아니더라도 점프를 할 수 있지만, 그 경우에는 항상 최적이 아니다.


간단한 반례를 들면, $i < j < k$이고 $arr[i] < arr[j] < arr[k]$라고 가정하자.
거리 조건을 모두 만족한다면, $k$에서 $i$로 바로 점프할 수 있지만 $j$를 항상 거쳐 가는 것이 더 좋다.


스택을 사용해서 각 인덱스마다 양쪽으로 점프할 수 있는 곳을 미리 구해두고,

원소가 큰 순서대로 방문하며 dp를 돌린다.

코드

class Solution {

    public int maxJumps(int[] arr, int d) {
        int N = arr.length;
        int[] left = new int[N];
        int[] right = new int[N];

        Stack<Integer> stack = new Stack<>();
        Arrays.fill(left, -1);
        for(int i=0;i<N;i++) {
            while(!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
                int idx = stack.pop();
                if(i - idx <= d) {
                    left[idx] = i;
                }
            }
            stack.push(i);
        }

        while(!stack.isEmpty()) stack.pop();
        Arrays.fill(right, -1);
        for(int i=N-1;i>=0;i--) {
            while(!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
                int idx = stack.pop();
                if(idx - i <= d) {
                    right[idx] = i;
                }
            }
            stack.push(i);
        }

        int[] dp = new int[N];
        Arrays.fill(dp, 1);
        int[][] infos = new int[N][];
        for(int i=0;i<N;i++) {
            infos[i] = new int[]{arr[i], i};
        }

        Arrays.sort(infos, (a,b) -> b[0]-a[0]);
        int answer = 1;
        for(int[] info : infos) {
            int idx = info[1];

            if(left[idx] != -1) dp[idx] = Math.max(dp[idx], dp[left[idx]] + 1);
            if(right[idx] != -1) dp[idx] = Math.max(dp[idx], dp[right[idx]] + 1);
            answer = Math.max(answer, dp[idx]);
        }

        return answer;
    }
}