[릿코드] 1345. Jump Game IV

문제 (2022.01.15)

https://leetcode.com/problems/jump-game-iv/

접근

처음에는 재귀함수를 사용하는 방법을 생각하고 이렇게 코드를 짰었다.

코드 1 - 재귀함수 사용

import java.util.*;

class Solution {
    int answer = Integer.MAX_VALUE;
    int[] arr;
    boolean[] visited;
    Map<Integer, List<Integer>> map = new HashMap<>();
    
    public int minJumps(int[] arr) {
        this.arr = arr;
        visited = new boolean[arr.length];
        
        for (int i = 0; i < arr.length; i++) {
            List<Integer> list = map.containsKey(arr[i]) ? map.get(arr[i]) : new ArrayList<>();
            list.add(i);
            map.put(arr[i], list);
        }
        
        func(0, 0);
        return answer;
    }
    
    public void func(int idx, int depth) {
        if (idx == arr.length - 1) {
            answer = Math.min(answer, depth);
            return;
        }
        
        if (depth >= answer) {
            return;
        }
        
        visited[idx] = true;
        
        if (idx - 1 >= 0 && !visited[idx - 1]) {
            func(idx - 1, depth + 1);
        }
        
        if (idx + 1 < arr.length && !visited[idx + 1]) {
            func(idx + 1, depth + 1);   
        }
        
        List<Integer> list = map.get(arr[idx]);
        for (Integer i : list) {
            if (!visited[i]) {
                func(i, depth + 1);
            }
        }
        
        visited[idx] = false;
    }
}

다음과 같은 테스트케이스가 들어온다면?
[7, 7, 7, ... 7] <- arr.length = 3000

재귀함수 깊이가 최대 3000이 될 것이다. 문제에서 배열 최대 길이가 50000이라고 했는데, 그럼 재귀함수의 최대 깊이는 50000이 될 것이고 이는 시간초과를 발생시킬 것이다. 따라서 재귀함수를 호출하지 않는 방향으로 고민해보고 큐를 사용하여 다시 풀게 되었다.

코드 2 - 큐 사용

import java.util.*;

class Solution {
    public int minJumps(int[] arr) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        boolean[] visited = new boolean[arr.length];
        
        for (int i = 0; i < arr.length; i++) {
            List<Integer> list = map.containsKey(arr[i]) ? map.get(arr[i]) : new ArrayList<>();
            list.add(i);
            map.put(arr[i], list);
        }
        
        Queue<Integer> q = new LinkedList<>();
        int count = 0;
        q.add(0);
        visited[0] = true;
        
        while(!q.isEmpty()) {
            int size = q.size();
            
            for (int i = 0; i < size; i++) {
                Integer index = q.remove();
                
                if (index == arr.length - 1) {
                    return count;
                }
                
                if (index + 1 < arr.length && !visited[index + 1]) {
                    q.add(index + 1);
                    visited[index + 1] = true;
                }
                
                if (index - 1 >= 0 && !visited[index - 1]) {
                    q.add(index - 1);
                    visited[index - 1] = true;
                }
                
                if (map.containsKey(arr[index])) {
                    List<Integer> indexes = map.get(arr[index]);
                    for (Integer idx : indexes) {
                        if (!visited[idx]) {
                            q.add(idx);
                            visited[idx] = true;
                        }
                    }
                    
                    map.remove(arr[index]); // 이 부분 중요!!!
                }
            }
            
            count++;
        }
        
        return 0;
    }
}

중간에 주석을 달아놓은 곳이 있다. 처음에는 저 부분을 작성하지 않았더니 역시나 시간초과가 나타났다. 처음에는 이렇게 생각했다. 큐에 집어넣을 때 visited도 체크해줬고, 도대체 뭐가 문제지...?

관련 코드를 약간 뜯어보자면,

import java.util.*;

class Solution {
    public int minJumps(int[] arr) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        boolean[] visited = new boolean[arr.length];
        
        ...
        
        while(!q.isEmpty()) {
            int size = q.size();
            
            for (int i = 0; i < size; i++) {
                Integer index = q.remove();
                
                ...
                
                if (map.containsKey(arr[index])) {
                    List<Integer> indexes = map.get(arr[index]);
                    for (Integer idx : indexes) {
                        ...
                    }
                    
                    // map.remove(arr[index]); 
                }
            }
            
            count++;
        }
        
        return 0;
    }
}

map에서 특정 값에 대한 요소를 삭제하지 않으면 이런 테스트케이스에서 문제가 발생하게 된다.

다음과 같은 테스트케이스가 들어온다면?
[7, 7, 7, ... 7] <- arr.length = 30000

1. 처음에 map에서 7에 대한 인덱스들이 30000개 들어갈 것이다. (arr의 모든 요소가 7로 이루어졌기 때문이다.)
2. count = 1일 때 (foreach문에서) 큐에 29999개의 인덱스가 들어갈 것이며 다 들어간 후 count = 2가 될 것이다.
3. 큐가 비지 않았으니 다시 for문이 돌 것이며, 큐에서 꺼낸 한 인덱스에 대해서 map에 있는지 조건문에 걸리게 될 것이다.
4. 원소는 역시나 7, map에는 당연히 있게 될 것이고 foreach문에서 30000만큼 또 돌 것이다. (원소 7에 대해서는 이미 큐에 들어있는 상태인데 또 돌 필요가 없어진다.)

이 한 줄 때문에 이상한 시도를 많이 하였고 시간을 오래 잡아먹었던 것 같다.