[leetcode][45] Jump Game II 문제풀기!
👓 문제 요약
처음 인덱스에서 마지막 인덱스에 도달하려면 몇 번 점프해야할까? 해당 인덱스에서 최대 얼마나 뛸 수 있는지는 알려줄게!
자세한 문제 설명과 릿코드 홈페이지 참고. 문제풀러가기
🔑 문제 풀이
주어지는 인풋의 길이가 최대 30,000 이기 때문에 최소 O(nlgn) 기법을 써야 합니다!
저는 탐욕 기법으로 해당 인덱스에서 뛰었을 때 최대로 가는 놈만 골라서 그냥 뛰었습니다!
🥽 소스코드 및 소스해석
var jump = function (nums) {
if (nums.length === 1) return 0;
if (nums[0] >= nums.length - 1) return 1;
let nowPos = 0;
let count = 0;
for (let i = 0; i < nums.length; ) {
let maxNum = 0;
for (let dist = 1; dist <= nums[i]; dist++) {
if (maxNum <= dist + nums[i + dist] || dist + i >= nums.length - 1) {
maxNum = dist + nums[i + dist];
nowPos = i + dist;
}
}
i = nowPos;
count++;
if (nowPos >= nums.length - 1) {
break;
}
}
return count;
};🔨 문제 후기
왜 hard 난이도 인지 알 수 없는 문제!! 끄앗!!!
Series
Algorithms
이 글은 "Algorithms" 시리즈의 27번째 기록입니다.
- 01#[프로그래머스][연습문제] 3 x N 타일링 풀이
- 02[프로그래머스][2019 kakao] 블록게임 해설
- 03[프로그래머스][2019 kakao] 길 찾기 게임 문제 해설
- 04[프로그래머스][2019 kakao] 무지의 먹방 라이브 문제 해설
- 05[프로그래머스][2019 kakao] 후보키 문제 해설
- 06[프로그래머스✈][2020 kakao] 자물쇠와 열쇠 문제 풀이
- 07[프로그래머스][2020 kakao] 기둥과 보 설치 문제 해설
- 08[프로그래머스✈][2020 kakao] 가사 검색 문제 풀이
- 09[백준🔉][16234] 인구이동 문제 해설
- 10[프로그래머스✈][2019 kakao 겨울 인턴십] 불량 사용자 문제 해설
- 11[프로그래머스✈][2020 kakao] 동굴 탐험
- 12[백준🔉][14501] 퇴사 문제 해설
- 13[프로그래머스✈][2017 카카오코드] 4단 고음 해설
- 14[프로그래머스✈][2019 kakao 겨울 인턴쉽] 징검다리 건너기 해설
- 15[프로그래머스✈][연습문제] 섬 연결하기 풀이
- 16[leetcode][15] 3sum 문제풀기!
- 17[leetcode][16] 3sum closet 문제풀기!
- 18[📣top interview question] Remove Duplicates from Sorted Array Solution 문제풀기!
- 19[📣top interview question] Best Time to Buy and Sell Stock II 문제풀기!
- 20[leetcode][30] Substring with Concatenation of All Words 문제풀기!
- 21[leetcode][31] Next Permutation 문제풀기!
- 22[leetcode][32] Longest Valid Parentheses 문제풀기
- 23[leetcode][40] Combination Sum II 문제풀기!
- 24[leetcode][42] Trapping Rain Water 문제풀기!
- 25[leetcode][43] Multiply Strings 문제풀기!
- 26[leetcode][44] Wildcard Matching 문제풀기!
- 27[leetcode][45] Jump Game II 문제풀기!