Jump Game III

문제 번호, 이름: 1306. Jump Game III

문제 링크: https://leetcode.com/problems/jump-game-iii/description/

날짜: 2024/06/30

상태: 완료

 

이 문제를 고른 이유

그냥?

문제 보고 처음 든 생각

그냥 traversal로 짬프 짬프 뛰어가며 구하면 되는 거 아닌가?

 

풀이 v1

• 소요 시간 15분

from collections import deque

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        len_arr = len(arr)
        visited_flags = [False for _ in range(len_arr)]

        stack = deque()
        stack.append(start)
        visited_flags[start] = True
        while True:
            if len(stack) == 0:
                return False
            idx = stack.pop()
            if arr[idx] == 0:
                return True
            if idx + arr[idx] < len_arr and not visited_flags[idx + arr[idx]]:
                stack.append(idx + arr[idx])
                visited_flags[idx + arr[idx]] = True
            if idx - arr[idx] >= 0 and not visited_flags[idx - arr[idx]]:
                stack.append(idx - arr[idx])
                visited_flags[idx - arr[idx]] = True

 

• 점프를 뛰어가다가 이미 방문했던 index를 만나면 어차피 더 뛰어봤자 이전에 traversal 했을 것이기 때문에 그 경우를 버리기로 했다. 그래서 visited_flags를 뒀다
• 풀이 자체는 머릿속에 금방 떠올랐는데 이게 왜 시간복잡도가 문제에서 요구하는 만큼 충분히 작은지 설명을 못 해서 그 고민을 하다가 시간이 많이 걸렸다. 결국 생각이 안 나서 일단 코드부터 짜 보기로 했는데 통과를 하길래 아 이게 맞구나.. 싶었다

풀이 v2

• 소요 시간 -

# if v2 exists

 

 

이 문제를 풀고 얻은 것

• 이젠 dfs(일부 유형)를 레퍼런스 안 보고 금방금방 짤 수 있다

메모

• 남의 풀이를 보고, 첫째로, 내가 visited_flag를 두고 체크했던 것을 완전 신기하게 푼 것을 발견했다. 문제에서 arr의 원소는 non-negative 라고 제한해줬기 때문에 visited index의 원소는 -1을 곱해버려서 음수로 만들고, 나중에 visited임을 판별할 때 원소가 음수인지 양수인지로 판별했다. 와 이러면 메모리를 O(n)만큼 덜 쓸 수 있다!
• 그리고 나는 dfs를 stack 자료구조를 이용한 iteration으로 풀었지만 다른 풀이를 보면 recursion을 사용해서 코드가 더 간결하긴 하더라
• 시간복잡도에 관해서는.. 각 index가 최대 1번만 접근되니까 O(n)이라는 설명.. 이 있었다. 확 이해되진 않았지만 언젠간 이해될 것이다