💬 문제
[문제 링크]
int 배열 nums가 주어지고 각 인덱스의 값은 이동할 수 있는 최대 거리
인덱스 0에서부터 출발해서 마지막 인덱스에 도착할 수 있는 최소 이동 횟수 구하기
무조건 도착할 수 있는 배열이며, 어디서든 최대로 점프해도 마지막 인덱스를 넘지 않음
✍️ 나의 풀이
/**
* @param {number[]} nums
* @return {number}
*/
var jump = function(nums) {
let jump = 0;
let goal = nums.length - 1;
if (goal === 0)
return 0;
while (goal !== 0) {
let max_idx = goal - 1;
for (let i = goal - 1; i >= 0; i--) {
if (nums[i] + i >= goal)
max_idx = i;
}
goal = max_idx;
jump++;
}
return jump;
};점프게임1과 같이 뒤에서부터 목적지를 수정해가며(goal) 계산
마지막 인덱스 앞에서부터 순차적으로 현재 목표 지점까지 갈 수 있는지 파악하여 가능한 가장 작은 인덱스 번호를 목표지로 설정
목적지 번호가 0이 될때까지 반복하고, 반복할 때마다 점프 1회로 생각
📌 결과
Accepted
Runtime 71ms (Beats 27.41%)
Memory 51.39MB (Beats 34.85%)
📚 러닝 포인트
드디어 혼자서 풀어냈다면서 좋아했는데 중첩 반복문을 사용했더니 성능이 너무 안좋게 나왔다. 처음에는 max_idx의 용도가 가장 큰 점프력을 가진 인덱스를 저장하는 것이었는데, 테스트를 하다보니 최대 점프력보다는 인덱스 번호가 앞쪽인 것이 더 중요했다. for문 안의 if문을 수정해서 통과하기는 했는데 결과가 찜찜해서 다른 솔루션도 찾아보니 엄청나게 쉬운 것을 발견했다.
**//Time Complexity : O(n), Space Complexity: O(1)**
var jump = function(nums) {
var jump = 0;
var prev = 0;
var max = 0;
for (var i = 0; i < nums.length - 1; i++) {
// Keep track of the maximum jump
max = Math.max(max, i + nums[i]);
// When we get to the index where we had our previous maximum jump,
// we increase our jump...
if (i === prev) {
jump++;
prev = max;
}
}
return jump;
};현재 인덱스에서 최대로 갈 수 있는 곳까지의 범위 안에서 가장 멀리 갈 수 있는 다음 인덱스를 찾는 방법이다. 따라서 그 안에서 최대로 갈 수 있는 곳을 찾으면 해당 인덱스를 max로 기억해두고, 시작했던 인덱스에서 갈 수 있던 최대 거리의 인덱스를 만나면 jump한 것으로 친다. 그렇게 반복하는 코드인데 이번에도 새로운 깨달음을 얻었다. 오기가 생겨서 한 문제 더 푼건데 이렇게 또 져버릴 줄이야... 그래도 스스로의 힘으로 통과는 했으니 다음번에는 더 발전할 거라 믿는다!
