[1주차] 55. Jump Game

https://leetcode.com/problems/jump-game/?envType=study-plan-v2&envId=top-interview-150

Jump Game - LeetCode

---

📄 문제

1차원 정수 배열 nums가 주어진다. 처음에 당신은 인덱스 0에 위치한다.

각 원소는 해당 인덱스에서 점프할 수 있는 최대 거리를 나타낸다.

점프를 반복하여 마지막 인덱스에 도달할 수 있으면 true, 불가능하면 false를 리턴하라.

 

 

🎈 풀이

점프할 수 있는 최대거리 라는 것은 반드시 최대거리로 점프할 필요가 없다는 것을 의미한다.

예를 들어, [10, 1, 4] 같은 경우 시작이 최대 10 거리를 점프할 수 있지만 마지막 인덱스에 도달하기 위해서는 2 혹은 1 만큼만 점프해야 한다.

또한, 도달할 수 있는 여부에 대해서만 묻고, 점프의 최소횟수는 요구하고 있지 않기 때문에, 10 -> 1 -> 4 방식으로 도달해도 답을 구할 수 있다.

도달 가능한 경우를 떠올려 보자.

• [1,1,1,1,1] 과 같이 모두 0보다 클 경우는 도달 가능하다.
• [2,0,1,1,1] 과 같이 0을 뛰어 넘을 수 있으면 도달 가능하다.

 

그렇다면 도달 불가능한 경우는 어떤 것이 있을까?

• 원소중 하나라도 0이 반드시 존재한다.
• [2, 1, 1, 0, 1] 과 같이 0의 이전 원소 중, 하나라도 0을 뛰어넘을 수 있는 원소가 존재하지 않는다.

 

 

그렇다면 이렇게 로직을 짤 수 있겠다.

• 마지막 인덱스 부터 0 까지 역순으로 탐색을 시작한다.
• 인덱스 0까지 탐색했는데 0을 발견하지 못했다 - true
• 0을 발견했다!!
  • 0 다음 인덱스를 탐색하며 0까지의 거리를 기록한다.
  • 0까지의 거리보다 현재 원소가 크다면 0을 뛰어넘을 수 있다는 것을 의미한다.
  • 인덱스 0까지 탐색했는데 뛰어넘을 수 있는 원소가 없다면 false 이다.

 

 

시간복잡도: O(n)

공간복잡도: O(1)

fun canJump(nums: IntArray): Boolean {
    var distanceFromZero = 0
    for (i in nums.lastIndex - 1 downTo 0) {
        if (nums[i] == 0) {
            // 0을 만났다!!
            distanceFromZero = 1
            continue
        }

        if (distanceFromZero != 0) {
            // 현재까지 뛰어넘지 못한 0이 존재
            if (nums[i] > distanceFromZero) {
                distanceFromZero = 0 //뛰어넘으면 0으로 세팅한다.
            } else {
                distanceFromZero++
            }
        }

        // distanceFromZero 가 0이면 극복가능한 0을 만났거나 0을 만나지 않은 상태이다.
    }

    return distanceFromZero == 0
}

 

완벽하다고 생각했는데 틀렸다. 내 로직은 0이 여러 개 일 때를 고려하지 않았다.

LeetCode는 틀렸을 때 케이스를 친절하게 알려준다. [2,0,1,0,1] 일 때 위의 로직은 true를 반환하므로 틀렸다.

현재 뛰어넘지 못한 0이 존재하고, 0을 또 만났다?

중간에 만난 0을 뛰어넘는건 의미가 없다. 아직 뛰어넘지 못한 0을 넘어야 마지막에 도달할 수 있기 때문이다.

그러므로 4행의 조건을 수정한다.

 

if (nums[i] == 0) {
    // 0을 만났다!!
    // 이미 0을 만났었다면 0으로 초기화하지 않는다.
    if (distanceFromZero == 0) { 
        distanceFromZero = 0
    }
    distanceFromZero++
    continue
}