[LeetCode] 1345번 Jump Game IV 문제를 풀어보았다. (ft. java)

2023년 03월 05일 일요일 - 오랜만이구만

오늘 올려볼 문제는 1345번 Jump Game IV 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

하드치고는 쉬웠다!

입력

사진에서도 볼 수 있듯이 int 배열 1개가 입력으로 들어온다.

---

풀이 및 코드

0번째 index에서 마지막 index로 가는 가장 짧은 점프 횟수를 구하는 문제이다.

아래 3가지 방법으로 점프가 가능하다.

1. 0보다 크거나 같은 index - 1
2. 배열의 크기보다 작은 index + 1
3. arr[i] == arr[j] 인 j

오늘은 처음부터 정답을 생각해냈다.

bfs를 하는데 이미 방문했던 곳은 다시 갈 필요가 없으므로 visit 배열도 만들어서 활용했다.

또한 이미 방문한 곳에 원소값에 해당하는 index들은 이미 queue에 들어갔거나 들어있으므로 다시 넣는 과정을 거치지 않는다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int minJumps(int[] arr) {
        var visit = new boolean[arr.length];
        var map = new HashMap<Integer, ArrayList<Integer>>();
        
        for(int i = 0; i < arr.length; i++) {
            var num = arr[i];
            if(!map.containsKey(num)) map.put(num, new ArrayList<>());
            map.get(num).add(i);
        }
        
        var q = new LinkedList<Integer>();
        q.add(0);
        
        for(int jump = 0; jump < arr.length; jump++) {
            int size = q.size();
            for(int i = 0; i < size; i++) {
                var now = q.poll();
                
                if(now == arr.length - 1) return jump;
                
                if(now - 1 > 0 && !visit[now - 1]) q.add(now - 1);
                if(!visit[now + 1]) q.add(now + 1);
                
                if(visit[now]) continue;
                
                visit[now] = true;
                
                for(var index: map.get(arr[now])) {
                    if(visit[index]) continue;
                    visit[index] = true;
                    q.add(index);
                }
            }
        }
        
        return arr.length - 1;
    }
}

---

제출 화면

생각보다는 오래걸렸는데 조금 처리를 잘못해서 오래걸린 것이라서 실수를 조금 덜하도록 노력해야 할 것 같다.

그래도 하드 문제인 것 치고는 잘 풀어서 맘에 든다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.