LeetCode 1871. Jump Game VII

 

 

문제

$0$과 $1$로만 이루어진 문자열 $s$가 주어진다.

문자열의 인덱스 $i$에서 $[i+\texttt{minJump}, i+\texttt{maxJump}]$ 범위 내의 값이 $1$인 인덱스로 점프할 수 있다.

단, 인덱스가 문자열의 경계를 넘어가서는 안 된다.

 

인덱스 $0$에서 $s.\texttt{length}-1$로 점프할 수 있는지 알아보자.

풀이

거꾸로 생각해보자. 인덱스 $i$로 도달할 수 있을 조건이 무엇일까?

$[i-\texttt{maxJump}, i-\texttt{minJump}]$ 범위에서 도달 가능한 인덱스 $j$가 적어도 하나 있어야 한다.

 

$\texttt{reach}[i]$를 인덱스 $i$로 도달 가능하면 true, 아니면 false라고 정의하자.

 

인덱스 $i$를 반복문으로 순회한다면, $[i-\texttt{maxJump}, i-\texttt{minJump}]$ 구간을 슬라이딩 윈도우로 관리할 수 있다.

정확히는, 해당 구간에 $\texttt{reach}$가 true인 인덱스의 개수를 $\textbf{count}$ 변수로 관리한다.

 

$i$가 증가할 때마다 $\texttt{reach}[i-\texttt{minJump}]$의 값을 $\textbf{count}$ 에 반영한다.

동시에, $\texttt{reach}[i-\texttt{maxJump}-1]$의 값을 $\textbf{count}$ 에서 제외한다.

 

코드

class Solution {

    public boolean canReach(String s, int minJump, int maxJump) {
        boolean[] reach = new boolean[s.length()];
        reach[0] = true;
        int count = 0;
        for(int i=minJump;i<s.length();i++) {
            if(reach[i-minJump]) count++;
            if(i-maxJump-1 >= 0 && reach[i-maxJump-1]) count--;
            reach[i] = s.charAt(i) == '0' && count > 0;
        }

        return reach[s.length()-1];
    }
}