Leet code - frog jump

문제 설명

개구리가 강을 건넌다.
배열에는 돌의 위치가 주어진다.
개구리는 돌에서 돌로만 jump 할 수 있으며, 물에 빠지면 안된다.

개구리가 jump 할 때는 이전에 jump한 거리를 k라고할때, k-1, k, k+1만큼 다음 jump를 할 수 있다.

개구리는 무사히 마지막 돌 위에 도착할 수 있는가?

해결방법

처음에 당연히 dp를 이용해서 jump할 수 있는 최댓값을 memorization을 하자.
일종의 greedy + dp일줄 알았는데, greedy를 적용할 수 없는 반례가 있더라.

따라서 각돌에 대해서 jump할 수 있는 거리들을 dp로 memorization해야하며,
중복된 값은 계산의 낭비만 불러오므로 memorization 할 값은
Hash Set으로 지정했다.

코드

class Solution {
    public boolean canCross(int[] stones) {
        if(stones[stones.length-1]>1100*1100) return false;
        
        
        HashMap<Integer, HashSet<Integer>> map = new HashMap<>();
        
        for(int i=0; i<stones.length; i++){
            if(i==0){
                HashSet<Integer> list = map.getOrDefault(1,new HashSet<Integer>());
                list.add(1);
                map.put(1,list);
                continue;
            }
            if(!map.containsKey(stones[i])) continue;
            for(int jump : map.get(stones[i])){
                try{
                    HashSet<Integer> list =
                        map.getOrDefault(stones[i]+jump+1,new HashSet<Integer>());
                    list.add(jump + 1);
                    map.put(stones[i] + jump + 1, list);
                }catch(Exception e){

                }
            
                try{
                    HashSet<Integer> list =
                        map.getOrDefault(stones[i]+jump,new HashSet<Integer>());
                    list.add(jump);
                    map.put(stones[i] + jump, list);
                }catch(Exception e){

                }
            
                try{
                    if(jump-1+stones[i] == stones[i]) throw new Exception("");
                    HashSet<Integer> list =
                        map.getOrDefault(stones[i]+jump-1,new HashSet<Integer>());
                    list.add(jump-1);
                    map.put(stones[i] + jump-1, list);
                }catch(Exception e){

                }
            }   
        }
        
        // System.out.println(map);
        
        return map.containsKey(stones[stones.length-1]);
    }
}

해결