코딩테스트(Kotlin)/LeetCode Top Interview 150

[1주차] 55. Jump Game

YJ_Lee 2023. 8. 25. 09:56

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

 

Jump Game - LeetCode

Can you solve this real interview question? Jump Game - You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position. Return true if you can

leetcode.com


📄 문제

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
}