마지막 칸까지 가는 최소 점프 수

자바스크립트 코딩테스트 문제로 greedy 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

today medium greedy 함수명: solution 제한 시간: 200ms

각 칸에서 앞으로 최대 nums[i]칸까지 점프할 수 있는 정수 배열 nums가 주어질 때, 첫 번째 칸에서 마지막 칸까지 도달하는 최소 점프 횟수를 반환하는 solution 함수를 작성하세요.

항상 마지막 칸까지 도달할 수 있다고 가정합니다.

제한사항

• 1 <= nums.length <= 100000
• 0 <= nums[i] <= 100000
• 시작 위치는 인덱스 0입니다.
• 항상 마지막 칸까지 도달할 수 있습니다.

예시

• 입력: [2, 3, 1, 1, 4] → 출력: 2
• 입력: [2, 3, 0, 1, 4] → 출력: 2
• 입력: [0] → 출력: 0

힌트

• 현재 점프 수로 갈 수 있는 구간을 하나의 묶음처럼 생각해 보세요.
• 그 구간 안에서 다음 점프가 닿을 수 있는 가장 먼 위치만 알면 됩니다.
• 구간 끝에 닿았을 때 점프 수를 하나 늘리면 됩니다.

해설

이 문제의 핵심은 BFS 레벨처럼 구간을 확장하는 greedy입니다.

1. 현재 점프 횟수로 도달 가능한 구간의 오른쪽 끝을 currentEnd로 둡니다.
2. 그 구간 안의 각 위치에서 i + nums[i]로 다음에 닿을 수 있는 가장 먼 위치 farthest를 갱신합니다.
3. 인덱스 i가 currentEnd에 도달하면, 지금까지 본 위치들로 만들 수 있는 다음 구간이 확정되므로 점프 횟수를 1 늘리고 currentEnd = farthest로 갱신합니다.
4. 마지막 칸 직전까지만 보면 최소 점프 횟수를 구할 수 있습니다.

예를 들어 [2, 3, 1, 1, 4]에서는:

• 처음 점프로 인덱스 0에서 시작해 1 또는 2까지 갈 수 있습니다.
• 그 구간에서 가장 멀리 뻗는 선택은 인덱스 1을 거쳐 마지막 칸 근처까지 가는 경우입니다.
• 따라서 최소 점프 수는 2입니다.

각 위치를 한 번씩만 보므로 효율적으로 해결할 수 있습니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

입력값 []

아직 실행하지 않았습니다.

실행 결과

아직 실행하지 않았습니다.

예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.

댓글

문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.