[스위프트][Leet Code - Jump Game 2][Medium] (그리디)
Categories: leetcode
🧞♂️ 난이도
Medium
🧞♂️ 문제
Jump Game2
🧞♂️ 유형
그리디
🧞♂️ 풀이
이 문제는 그리디하게 최고의 jump 방법을 기록해뒀다가 나중에 jump한 인덱스를 만나면 정답에 추가하는 방법으로 풀 수 있다.
다음 두개의 변수로 풀 수 있다.
maxJumpIndex: 가장 먼 점프를 했을때 도착하는 인덱스(계속 갱신)
jumpedIndex: jump 를 실시해서 도착한 인덱스
예를 들어
[2, 3, 1, 1, 4] 이렇게 입력값이 주어지면
index: 0 ( maxJumpIndex: 2 (0 + num[i]) / jumpedIndex = 2로 갱신하고 answer에 추가) index: 1 ( maxJumpIndex: 4 (1 + num[i]) / jumpedIndex = 2) index: 2 ( maxJumpIndex: 4, jumpedIndex = 4 로 갱신하고 answer 추가)
이렇게되면 0번째 인덱스에서 1번째 인덱스로 뛰고, 1번째 인덱스에서 4번째 인덱스까지 뛰어서 2번 만에 끝까지 갈 수 있게 된다.
이게 왜 가능하냐면, 첫번째 인덱스에서 2만큼 뛸 수 있지만, 1만큼만 뛸 수도 있다. 그렇기때문에 가장 멀리 뛸 수 있는 방법을 저장해뒀다가, 그게 최적의 방법인걸 알았을때(1만큼 뛰는게 좋을지 2만큼 뒤는게 좋을지는 2만큼 뛴 곳에서 알 수 있다) 선택을 하는 방법이다.
즉, 인덱스가 0일때, 0+2 번째 인덱스까지 가보고 어디까지 뛸지 선택을 하는 것이다.
🧞♂️ 스위프트 풀이
class Solution {
func jump(_ nums: [Int]) -> Int {
var answer = 0
var maxJumpIndex = 0
var jumpedIndex = 0
for i in 0..<nums.count - 1 {
maxJumpIndex = max(maxJumpIndex, i + nums[i])
if i == jumpedIndex {
jumpedIndex = maxJumpIndex
answer += 1
}
}
return answer
}
}