LeetCode 55 Jump Game 풀러가기

문제

문제 분석

첫번째 시도

Queue를 활용한 BFS 방식을 활용했다.

가능한 모든 index를 Queue에 넣으면서 배열의 끝에 도달한다면 true를 반환하도록 코드를 구현했다.

결과 : 시간 초과

코드

import java.util.*;

class Solution {
    public boolean canJump(int[] nums) {
        Queue<Integer> queue = new LinkedList<>();

        queue.add(0);

        while(!queue.isEmpty()){
            int temp = queue.poll();

            if(temp == nums.length -1) return true;

            for(int i=1; i<=nums[temp]; i++){
                int index = temp + i;
                if(index == nums.length-1)return true;
                else {
                    if(index < nums.length -1)queue.add(index);
                }
            }
        }

        return false;
    }
}

두번쨰 시도

시간 초과를 줄이기 위해

Queue에 index를 넣을 때 이미 방문된 index는 검사하지 않아도 되기 때문에 제외 시켰다.

이를 위해 방문 체크를 하는 boolean 배열(visited)을 만들었다.

코드

import java.util.*;

class Solution {
    public boolean canJump(int[] nums) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[nums.length];

        queue.add(0);
        visited[0] = true;

        while(!queue.isEmpty()){
            int temp = queue.poll();

            if(temp == nums.length -1) return true;

            for(int i=1; i<=nums[temp]; i++){
                int index = temp + i;

                if(index < nums.length&& !visited[index]){
                    queue.add(index);
                    visited[index] = true;
                }
            }
        }

        return false;
    }
}

결과 : 성공

Runtime

Memory

시간 초과는 통과했지만, 여전히 시간이 길었다.

세번째 시도

문제의 목표가 last index 도착이기 때문에, 가장 큰 index를 우선순위를 둔 queue를 활용해보았다.

코드

import java.util.*;

class Solution {
    public boolean canJump(int[] nums) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        boolean[] visited = new boolean[nums.length];

        queue.add(0);
        visited[0] = true;

        while(!queue.isEmpty()){
            int temp = queue.poll();

            if(temp == nums.length -1) return true;

            for(int i=1; i<=nums[temp]; i++){
                int index = temp + i;

                if(index < nums.length&& !visited[index]){
                    queue.add(index);
                    visited[index] = true;
                }
            }
        }

        return false;
    }
}

결과 : 성공

Runtime

Memory

시간이 우선순위 큐 덕분이지, 일반 큐보다 500ms 줄었지만, 여전히 실행시간이 너무 길었다.

네번째 시도

Queue 를 사용하지 않는 방법을 생각해보았다.

문제의 목표가 배열의 끝까지 가는 것이기 때문에, index를 계속 더해주면서 그 max 값만 더하도록 만들었다.

또한, 계속 갱신되는 index를 for문 안에 넣어서 모든 경우의 수를 갈 수 있도록 했다.

코드

import java.lang.Math;
class Solution {
    public boolean canJump(int[] nums) {
     int index = 0;
     for(int i =0;i<=index;i++) {
         index = Math.max(index,i+nums[i]);
         if(index >=nums.length-1)
         return true;
    } 
    return false;
    }
}

결과 : 성공

Runtime

Memory

시간이 확 줄은게 눈에 보인다.