sean.jin
Spark Code Blog
sean.jin
전체 방문자
오늘
어제
  • 분류 전체보기
    • 개발공부
      • Kotlin
      • LeetCode
      • Algorithm
      • React
    • 주식차트
    • 책리뷰
    • 유틸리티

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 책리뷰
  • 부의 추월차선
  • 쿼드러플위칭데이
  • 주식입문자
  • 변동성
  • 책
  • 주식투자
  • 초보
  • 오
  • 네마녀의날
  • 경제
  • 주식책리뷰
  • 아빠와 딸의 주식투자 레슨
  • 자기개발
  • 트리플 위칭데이
  • 책추천

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
sean.jin
개발공부/LeetCode

[JavaScript]45. Jump Game II

[JavaScript]45. Jump Game II
개발공부/LeetCode

[JavaScript]45. Jump Game II

2022. 3. 31. 10:51
반응형

45. Jump Game II

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

 

Example 1:

 

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

 

Example 2: 

Input: nums = [2,3,0,1,4]
Output: 2

 

Example 3: 

 

 

계획

array에 위치한 숫자는 그자리에 도착했을때 그자리에서 움직일수있는 칸수입니다. 그리고 가장 빠른 경로를 찾으면됩니다. 

 

그리고 앞으로 이동할때는 두가지 선택이있습니다. 그냥 한칸 움직이거나, 그 위치에 있는 숫자만큼 움직일수있습니다.

 

가장 빠른 경로를 찾는게 이 문제에서 찾아야하는 것입니다. 

 

 

구현 전략

2에서 시작하고 2의 레벨을 0이라 생각합니다. 그리고, 2에서 갈수있는 2가지 경로 3 과 1 을 레벨 1로 생각합니다. 그리고 다음레벨에 있는 1과 4가 레벨 2라 지정하면, 우리는 2번에 끝까지 도달할수있는 것을 알수있습니다. 

 

BFS와 유사한 성격을 가졌다고 할수있습니다. 

 

 

 

해설

var jump = function(nums) {
	if(nums.length === 1) return 0;  //우선 length가 1이면 점프가 필요없습니다. 
	let jumps = 0; //점프의 시작은 0으로 시작합니다. 
	let maxReach = nums[0]; // 지금까지 최대로 도달한위치
	let steps = nums[0]; //현재 위치
	for(let i = 1; i < nums.length - 1; i++){
		maxReach = Math.max(maxReach, i + nums[i]) //현재 최대로 도달한위치와 
		steps--; //
		if(steps === 0){
			jumps++;
			steps = maxReach - i;
		}
	}
	return jumps + 1;  
};
반응형

'개발공부 > LeetCode' 카테고리의 다른 글

171. Excel Sheet Column Number - 쉬운설명 반복문 사용  (0) 2022.04.05
[Javascript] 13. Roman to Integer 쉬운설명 - 해시맵  (0) 2022.04.05
[JavaScript] 991. Broken Calculator 쉬운 설명  (0) 2022.03.24
[Javascript] 1663. Smallest String With A Given Numeric Value -쉬운 설명  (0) 2022.03.22
[JavaScript] 36. Valid Sudoku  (0) 2022.03.20
  • 45. Jump Game II
  • 계획
  • 해설
'개발공부/LeetCode' 카테고리의 다른 글
  • 171. Excel Sheet Column Number - 쉬운설명 반복문 사용
  • [Javascript] 13. Roman to Integer 쉬운설명 - 해시맵
  • [JavaScript] 991. Broken Calculator 쉬운 설명
  • [Javascript] 1663. Smallest String With A Given Numeric Value -쉬운 설명
sean.jin
sean.jin
앱개발, 알고리즘, JS, Kotlin, 미국 취업준비

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.