참고
문제해설
NOTE
•
입력 값 ⇒ 점프 길이를 가지고 있는 정수 배열
•
출력 값 ⇒ 마지막 지점에 도달할 수 있는지 boolean 값
문제 로직고민
NOTE
•
시작지점부터 끝점까지 순회시켜 점프로 도착할 수 있는 모든 공간을 확인한다.
◦
Queue를 이용해서 점프할 수 있는 공간에 대해서 넣어준다.
◦
중복되는 값은 boolean[]을 생성해 체크한다.
◦
마지막 요소에 도달할 수 있게되면 순회를 멈춘다.
작성코드
NOTE
class Solution {
public boolean canJump(int[] nums) {
Queue<Integer> queue = new LinkedList();
boolean[] visited = new boolean[nums.length];
boolean result = false;
queue.add(0);
visited[0] = true;
while(!queue.isEmpty() && !result){
int idx = queue.poll();
int jump = nums[idx];
for(int i = 0; i <= jump; i++){
if(idx + i >= nums.length) break;
if(idx + i == nums.length - 1) result = true;
if(!visited[idx+i]){
visited[idx+i] = true;
queue.add(idx+i);
}
}
}
return result;
}
}
Java
복사
•
성능적으로 그렇게 좋아보이진 않는다.
정답코드
NOTE
class Solution {
public boolean canJump(int[] nums) {
boolean[] reach = new boolean[nums.length];
reach[0] = true;
for(int i=0; i< nums.length && reach[i]; i++){
int limit = Math.min(nums.length-1, nums[i]+i);
for(int j=limit; j>i && !reach[j] ; j--){
reach[j] = true;
}
if(reach[reach.length-1]){
break;
}
}
System.gc();
return reach[reach.length-1];
}
}
Java
복사
메모리를 가장 적게 사용하는 코드
•
Queue를 사용하지 않고, for문만으로 해결한 코드이다.
class Solution {
public boolean canJump(int[] nums) {
if (nums[0] == nums.length - 1) return true;
PriorityQueue<Integer> heap = new PriorityQueue<>(nums.length);
heap.add(nums.length - 1);
for (int i = nums.length - 2; i > 0; --i) {
if ((i + nums[i]) >= heap.peek()) {
heap.add(i);
}
}
return nums[0] >= heap.peek();
}
}
Java
복사
시간이 가장 빠른 코드
•
우선순위 큐를 사용한 코드이다.
•
나와달리 역순으로 탐색해서 점프가 가능한 공간이 있는지 탐색하고 있다.
•
이 경우 탐색이 훨씬빨라지기 때문에, 나보다 5배정도 빠르게 처리가능한것 같다.