Week 1-1. [Array / String] 55. Jump Game

문제 해결 과정

✍️ 나만의 방식으로 문제 정리하기 (=체계화)

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

Jump Game - LeetCode

배열의 각 위치에서의 최대 점프 길이가 주어진다. 마지막 인덱스에 도달할 수 있으면 true, 없으면 false를 반환하라.

• 입력
  • nums | int arrray := 각 인덱스에서 최대 점프 길이, | nums | ∈ [1, 10^4]
• 출력
  • isReachable | boolean := 마지막 인덱스 도달 여부
• 조건
  • | nums[i] | ∈ [0, 10^5]

 

🔎 어떤 식으로 접근했는가?

문제를 보자마자 어떤 식으로 접근해야할 지 막막했다.

각 배열에 담긴 수는 단순히 점프 거리가 아닌, "최대" 점프 거리였기 때문이다.

 

주어진 테스트 케이스를 보며 곰곰히 생각하다가, 주어진 배열에서 첫 번째와 맨 마지막 사이의 값들 중 0이 있으면 무조건 맨 마지막 인덱스에 도달할 수 없다는 사실을 발견했다.

 

이 방법은 "최대" 점프 거리를 신경쓰지 않아도 됐기에 바로 구현해보았으나 히든 케이스를 통과하지 못했다.

 

🙈 알고리즘 선택: 입력의 크기를 바탕으로

prices의 최대 길이가 10,000이므로 이중 for문까지 아슬아슬하게 감당할 수 있을 것으로 생각된다.

가능하다면 단일 for문만으로 구현하는 것이 좋겠지만.

 

📝 의사 코드

isReachable = true // 마지막 인덱스까지 도달할 수 있는지 체크
for (0; (nums길이-1)까지; 1씩 증가) {
	if (nums[i]가 0이라면) {
    	isReachable에 false 대입
    }
}
isReachable 반환

 

🎯 구현 코드

아래 코드는 공개 케이스는 통과하지만 히든 케이스까지는 통과하지 못한다.

class Solution {
    public boolean canJump(int[] nums) {
        boolean isReachable = true;
        for (int i=0; i<nums.length-1; i++) {
            if (nums[i] == 0) {
                isReachable = false;
            }
        }
        return isReachable;
    }
}

 

내 코드를 탐구해보기

⏱ 성능 측정 (시간복잡도/공간복잡도)

단일 for문을 사용하여 시간 복잡도는 O(N)이다.

 

✍️ 성능 회고

N은 최대 10,000이므로 감당할 수 있는 범위이다.

 

보통 1초 제한이라고 할 때, O(N)은 약 1억까지 O(N^2)은 약 1만까지 감당할 수 있다.

따라서 2중 for문까지도 사용할 수 있다.

 

💡 무엇을/어떻게 개선할 수 있을까?

nums가 [2, 0, 0]으로 주어질 때 테스트 케이스를 통과하지 못한다.

첫 번째 값과 마지막 값 사이에 0이 있음에도 마지막 값에 도달할 수 있기 때문이다.

 

주어진 요구사항을 만족할 수 있도록 다른 방법을 생각해야 한다.

 

다른 사람의 코드를 탐구해보기

🎯 구현 코드

nums 배열을 순회하며 각 단계에서 도달 가능한 가장 먼 인덱스(reachable)를 갱신한다.

계속해서 순회하다가 reachable이 i보다 작아진다면 더이상 전진할 수 없으므로 false를 반환한다.

class Solution {
    public boolean canJump(int[] nums) {
        int reachable = 0; // 각 단계에서 도달 가능한 가장 먼 인덱스
        for (int i=0; i<nums.length; i++) {
            if (i > reachable) { // 도달할 없는 인덱스를 발견하면 false 반환
                return false;
            }
            // ✅ 각 단계에서 도달 가능한 가장 먼 인덱스를 추적한다.
            reachable = Math.max(reachable, i+nums[i]);
        }
        // 반복문을 빠져나왔다면 마지막 인덱스에 도달할 수 있는 것이다.
        return true;
    }
}

 

⏱ 성능 측정 (시간복잡도/공간복잡도)

단일 for문을 사용하여 시간 복잡도는 O(N)이다.

 

느낀 점

이 문제를 어렵게 생각했던 이유는, "만약 nums[0]이 3이라면 1칸 점프, 2칸 점프, 3칸 점프의 경우의 수를 모두 나누어야 하나?" 라는 고민을 했기 때문이다.

 

i로 nums를 순회하면서 각 단계에서 도달할 수 있는 가장 먼 인덱스를 갱신하고, 이를 i와 비교하여 더 이상 전진할 수 없는 순간을 찾을 수 있었다.