[leetcode][45] Jump Game II

문제 : https://leetcode.com/problems/jump-game-ii/

---

음수가 아닌 정수 배열이 주어진다. 

배열 값은 그 인덱스에서 1번의 점프로 최대 몇 개의 인덱스를 이동할 수 있는지를 의미한다.

즉, arr[3] = 2인 경우 3인덱스에서 4, 5로 이동할 수 있다. (4, 5로 이동할 때 1번 점프로 이동가능을 의미)

0인덱스에서 시작할 때, 최소 몇 번의 점프로 마지막 인덱스까지 도달할 수 있는가.

(마지막 인덱스까지 도달할 수 없는 경우는 없다고 한다.)

---

그리디로 해결가능하다.

0부터 탐색하면서 탐색 중인 인덱스까지 도달하기 위해 필요한 최소 점프횟수(ans), 최대로 이동할 수 있는 인덱스(maxInd), 그리고 임시 최대이동가능 인덱스(tmp)를 구한다.

 

tmp는 임시로 저장해두었던 최대 이동 가능 인덱스에 탐색중인 인덱스가 도달했을 때, maxInd 값으로 갱신된다. tmp가 갱신될 때, ans를 +1씩 해준다.

 

[2, 3, 1, 1, 4]를 예로 들어보자.

시작 ans, tmp, maxInd 는 전부 0이다.

 

인덱스 0 탐색 :

maxInd는 2로 갱신된다.

tmp는 0이고 탐색 인덱스가 0에 도달했기 때문에 현재 maxInd인 2로 갱신된다.

tmp가 갱신되기 때문에 ans +1을 해서 ans는 1로 갱신된다.

 

인덱스 1 탐색 : maxInd는 4로 갱신. tmp는 갱신되지 않는다. ans도 갱신되지 않는다.

 

인덱스 2 탐색 : maxInd는 갱신되지 않는다. 현재 tmp는 2인데 탐색인덱스도 2이기 때문에 tmp는 maxInd 값인 4로 갱신되고 ans도 2로 갱신된다.

 

인덱스 3 탐색 : maxInd는 갱신되지 않는다. tmp, ans 미갱신.

 

인덱스 4 탐색 : maxInd는 8로 갱신. 이 때, 인덱스 4는 마지막 인덱스로 도달했기 때문에 ans 는 갱신하지 않아도된다.

 

즉, 정답은 ans인 2가 된다.

 

예로 하나를 들어봤으면 tmp 값이 무슨 값인지 감이 잡힐수도 있다.

tmp는 현재의 인덱스에서 한 번의 점프로 갈 수 있는 최대 인덱스이다. 즉, 현재 인덱스에서 tmp 인덱스까지는 한 번의 점프로 커버가 가능할 수 있다는 뜻이다.

문제는 언제 갱신되는가인데. 예시에서는 0, 2에서 갱신된다.

0에서는 시작인덱스가 0이기 때문에 갱신된다. 이 때, tmp는 현재 인덱스에서 한 번의 점프로 갈 수 있는 최대인덱스인 2로 갱신된다.

최대 2 인덱스까지는 한 번의 점프로 이동가능하기 때문에, 인덱스 1은 무시하고 2번째 인덱스일 때 갱신해야한다.

인덱스2에서 maxInd는 ~2 인덱스를 지나오면서 갈 수 있는 최대 인덱스이다. tmp인 2는 ~2 인덱스까지는 한 번의 점프로 이동이 가능하다는 의미이다. 따라서 2 이후부터는 반드시 한 번의 점프가 더 필요한데 이 때 뛰는 점프에서 어디까지 다시 갈 수 있는지를 갱신하는 것이다. 그게 maxInd인 4가 되는것이다. 이 때 점프 한 번이 더 필요하므로 ans에 +1을 해준다. 2 이후부터 반드시 한 번의 점프가 필요하다고 했는데, 이 점프를 반드시 2에서 한다는 뜻은 아니다. 이 점프는 1에서 할수도 있고 2에서 할 수도 있다. tmp는 2 인덱스까지 한 번의 점프로 이동가능하다는 뜻이었기 때문에 0 -> 1로 한 칸 점프후 거기서 다시 점프할수도 있기 때문이다. 따라서 현재 위치에서 최대로 이동가능한 곳으로 갱신하는게 아닌 maxInd를 사용할 수 있는 것이다.

 

시간복잡도는 O(N). N은 배열의 크기.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/45.%20Jump%20Game%20II.cpp