LeetCode 55. Jump Game

문제 링크

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

문제 해석

• nums 는 숫자 배열 , index 는 처음 0 에 위치
• 각 요소는 현재 위치에서 뛸 수 있는 최대 점프 거리 제공
• last index 에 도달 가능시 true return , 그렇지 않으면 false return

문제 해결

문제를 보고 , bfs 처럼 visited 배열을 만들고 탐색을 하는 건 줄 알았으나 , 생각해보니 그냥 순차적으로 한칸씩 이동만 시키면 되기때문에 최대 도착지 를 저장하는 변수를 만들어서 해결했다.

• index 의 최대 index를 지정해 index 랑 최대 index가 같으면 더 못가므로 false return
• max_index 가 nums-1 보다 크거나 같을시 true return

슈도 코드

index = 0
max_index = nums[index]
while True:
	if(max_index>=nums.length-1)
    	return true
  	if(max_index==index)
    	return false
    index +=1
    if(index+nums[index]>max_index)
    	max_index = index + nums[index]

• [0] 하나만 들어와도 max_index 0 , nums.length-1 도 0이므로 통과

결과

• 반복할때마다 , 미세하게 오차는 남.

사담

역시 Medium 이나 꽤나 쉬웠다. 백준이나 다른 문제들은 생각할 시간은 길게 요구하는데 , 앞부분이기도 하고 , 문제들이 되게 명확하게 제시해서 그런거 같다.

• 이렇게 , 끝에서부터 앞으로 가는 코드도 있는데 , 이게 더 시간은 짧게 끝났다.

메모본