[Algorithm] LeetCode 55 - Jump Game in Python(파이썬)

💡 LeetCode 55:

주어진 숫자 배열을 통해 최대 점프할 수 있는 길이 탐색

🌱 코드 in Python

알고리즘: Brute Force

class Solution(object):
    def canJump(self, nums):
        idx = 0
        for n in nums:
            if idx < 0:
                return False
            idx = max(n, idx)
            idx -= 1
        return True

이런 문제를 볼 때마다 무조건 경우의 수로 접근해서
쉬운 문제를 복자바게 푸려는 경향이 있다.. 🥲
그만큼 아직 내가 통찰력이 부족한 거게찌..
문제를 일단 정말 많이 풀어봐야 할 것 같다 흑흑

아무튼 이번 문제는 정확히 마지막 인덱스에 도달해야하는 문제가 아니다.
갈 수 있는 길이가 배열의 길이보다 긴가!만 확인하면된다.

따라서 배열을 순차로 확인하면서 갈 수 있는 최대 길이를 갱신한다.
그리고 한 칸 전진할때마다 갈 수 있는 길이를 1 감소 시킨다.
이렇게 하면 어떤 칸을 밟고 갔는가와 무관하게 갈 수 있는 최대 길이를 알 수 있다.

이렇게 간단한 풀이라니!

근데 이걸 brute force라고 할 수 있나?!

🧠 기억하자

1. 문제에서 원하는 바를 명확히 파악하자!

LeetCode 55 바로가기