4 분 소요

Array

문제

문제 링크

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 reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 105

    스스로 고민

접근법

  • 문제를 똑바로 이해를 못해서 시간을 정말 많이 사용한 것 같다.
  • 처음 index에서 시작되고 처음에 있는 숫자가 2라면 최대 점프 길이가 2다.
    • 처음에 무조건 2로 점프해야 되는 줄 알고 삽질을 정말 많이했다.
  • 각각 도전 횟수를 조절해서 마지막 인덱스에 접근이 가능하면 true 아니면 false

의사코드

  • 문제를 잘못이해 해서 시간이 오래걸리기도 했고 뭔가 방법이 잘 생각이 안나서 자료구조에 대해서 찾아보니 stack으로 구현해보면 될거 같았다.
  • nums 의 마지막 인덱스 값을 찾음
  • 처음 시작 인덱스가 마지막 인덱스인지 확인한다 맞으면 True 반환
  • 처음 인덱스가 마지막 인덱스와 일치하지 않을 경우 인덱스에 해당하는 숫자만큼 점프
  • 점프한 곳의 인덱스가 마지막 인덱스와 맞는지 확인
  • 현재 인덱스가 마지막 인덱스보다 작다면 점프한 곳의 인덱스에 해당하는 숫자만큼 또 다시 점프
  • 점프한 곳의 인덱스가 마지막 인덱스와 맞는지 확인
  • 만약 점프한 곳의 인덱스가 마지막 인덱스를 넘었다면 현재 인덱스의 숫자를 하나 씩 감소하면서 시도
  • 0이 될 때까지 시도한 후 그래도 실패한다면 그 전 숫자를 -1 해서 다시 시도 한 후 반복 진행

구현코드

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        last_index = len(nums)-1
        current_index = 0
        move_index = 0
        stack = []
        last_try = 0
        is_ture = len(nums) * 10
        while is_ture:
            # 처음 시작 인덱스가 마지막 인덱스가 맞는지 확인
            if current_index == last_index:
                return True
            elif current_index < last_index:
                # nums의 첫 번째 인덱스에 있는 숫자를 move_index로 만듦
                move_index = nums[current_index]
                
                # jump할 거리를 stack에 저장
                stack.append(move_index)
                
                # 점프한 후 현재 인덱스 업데이트
                current_index += move_index
                if move_index == 0:
                    stack.pop()
                if move_index == 0:
                    if current_index == 0:
                        return False
                    else:
                        last_try = stack.pop()
                        current_index -= last_try
                        last_try -= 1
                        if last_try == 0:
                            if len(stack) == 0:
                                return False
                            last_try = stack.pop()
                            current_index -= last_try
                            last_try -= 1
                            if last_try == 0:
                                if len(stack) == 0:
                                    return False
                                else:
                                    last_try = stack.pop()
                                    current_index += last_try
                                    stack.append(last_try)
                            else:
                                current_index += last_try
                                stack.append(last_try)
                        else:
                            current_index += last_try
                            stack.append(last_try)
            else:
                # current_index가 last_index를 초과한 경우
                # 마지막 시도한 점프 값을 뽑아냄
                last_try = stack.pop()
                if last_try == 0:
                    last_try = stack.pop()
                else:
                    # 현재 인덱스 이전으로 복귀
                    current_index -= last_try
                    
                    # current_index 업데이트
                    last_try -= 1
                    current_index += last_try
                    stack.append(last_try)
            is_ture -= 1
            if is_ture == 0:
                return False
  • 계속 오류가 났다. 잠깐 쉬었다가 내일 하면 다시 생각날거 같은데 한 번 막히니까 도저히 생각이 안났다. 그래서 그냥 오류 부분만 계속 고치면서 무지성으로 코드를 만들었다.
  • 하지만 뭔가 고치면 오류가 하나씩 새로 발견되고 그 부분을 고치다보니 자꾸 지저분해졌다.
  • 현재 이렇게 흘러간다는 건 기본적으로 뭔가 논리 자체에 오류가 있다고 생각했고 뭐가 문제인지 다시 생각해봤다.

구현 코드

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        last_index = 0  # 현재까지 최대로 도달할 수 있는 위치
        for i in range(len(nums)):
            if i > last_index:
                # 현재 위치까지 도달할 수 없으면 중단
                return False  
                
            # 현재 위치에서의 최대 도달 가능 위치 갱신
            last_index = max(last_index, i + nums[i])  
	            
            if last_index >= len(nums) - 1:
                return True  # 마지막 인덱스까지 도달할 수 있으면 성공
        return False
  • 모르겠어서 처음부터 다시 했다.
  • 너무 복잡하게 생각해서 단순하게 최소한의 값만 저장해서 찾는 방법을 생각해봤다.
  • 우선 마지막 인덱스는 무조건 필요하니까 해당 값만 갖고 찾을 방법이 있을지 생각해봤다.
  • i 는 현재 위치 nums[i] 는 최대 이동 가능한 칸 수
  • 이 중에 가장 높은 값으로 last_index를 갱신해주면서 도달 가능한지 못 한지 찾을 수 있다.

시간 복잡도와 공간 복잡도

시간 복잡도

  • 주어진 배열을 한 번 순회하면서 각 위치에서의 최대 이동 가능한 인덱스를 계산하고, 이를 통해 마지막 인덱스까지 도달 가능한지 판단한다. 배열의 길이를 n이라고 할 때, 코드는 n번의 순회를 수행하며 각 순회에서 상수 시간 연산이 이루어진다. 따라서 전체 코드의 시간 복잡도는 O(n) 다.

공간 복잡도

  • 주어진 코드에서 사용되는 추가적인 공간은 last_index 변수 하나뿐이다. 이 변수는 상수 공간을 사용하므로, 공간 복잡도는 O(1) 다.

회고 과정

지금 코드에서 뭘 개선할 수 있지?

  • 코드 문제 보다는 근본적인 문제가 크다고 생각했다.
  • 우선 계속 문제를 풀다보니까 메모리가 어떻게 차게 되는지 어떤 방식으로 진행하는게 효율적인지 그런 기본적인 부분에 대한 생각 없이 그냥 했던 것 같다.
  • 결국 처음부터 똑바로 하지 않으면 나중에 더 힘들어 지므로 꼭 위와 같은 생각을 하면서 코드를 작성하는 습관을 들여야 될 것 같다.

다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        target = len(nums) - 1
        idx = target - 1
        while idx >= 0:
            if idx + nums[idx] >= target:
                target = idx
            idx -= 1
        return target == 0
  • while 문 써서 해결해보려고 했는데 시간이 없어서 그냥 for 문으로 문제를 풀었는데 다음에는 강제적으로 while문으로 풀어 봐야겠다.
  • 위 코드는 시간 복잡도와 공간 복잡도는 다르지 않지만 개인적으로 가독성도 좋고 코드를 파악하는데 매우 쉽다고 생각헀다.
  • 맨 처음에 만든 코드같이 만들면 다른 사람이 봤을 때 파악하기 매우 어렵고 심지어 시간이 지난후 내가 다시 본다면 잘 기억하지 못 할 것 같다.
  • 이에 대해서 생각이 들었던 부분은 도저히 깔끔한 방법이 기억나지 않는다면 처음부터 다시 시작하는 방법 그리고 주석을 잘 달아놔야 겠다고 생각했다.

댓글남기기

참고