[Codility(코딜리티)] Lesson 13. FibFrog (100%)

Lesson 13 Fibonacci numbers - Fibonacci numbers (Java Solution)

app.codility.com/programmers/lessons/13-fibonacci_numbers/fib_frog/

FibFrog coding task - Learn to Code - Codility

---

문제

개구리가 -1에서 N까지 도달해야 한다
개구리는 F(K)로 점프할 수 있다 (F는 F(0) = 0 , F(1) = 1, F(M) = F(M-1) + F(M-2) If M>=2 (피보나치))
배열 A가 주어지는데, 0은 나뭇잎이 없고, 1은 나뭇잎이 있다
1을 통해 건너가야 한다
목표는 점프를 최소로 해서 목적지에 도달하는 것이다
예를 들면 int [] A = {0,0,0,1,1,0,1,0,0,0,0} 이면,
F(5) = 5, F(3) = 2, F(5) = 5로 총 3번 만에 도달하므로 3을 리턴한다

 

해결

우선 개구리가 점프할 수 있는 F를 구해놓는다

피보나치를 그냥 재귀로 구할경우 매번 계산하는 비용이 비싸므로 

fiboMap을 정의한 후, 개구리가 도달해야하는 지점 N+1까지만 계산한 후 넣는다

fiboMap 리스트로 바꾼 후, 가장 큰 값부터 정렬한다 

Point라는 클래스를 하나 정의한다

현재 위치 x와 점프횟수 y를 가진다

그리고 큐를 하나 만들고, 시작점 x=-1, y=0을 넣어 큐가 비어있을때까지 반복한다

fibo 리스트 중, 큰 값부터 순회하면서 도착점에 갈 수 있는지 체크한다

도착점이 아니라면, 값이 1인 (나뭇잎이 존재하는) 지점에 도착하면 y값을 하나 늘려주고 해당 위치 x와 y를 큐에 다시 넣는다

또한, 큐에 이미 한번 들어간 인덱스는 제외해야하므로 boolean[] check 배열로 조건에 넣어준다

 

public class FiboFrog {
    final static Map<Integer, Integer> fiboMap = new HashMap<>();

    public int solution(int[] A) {
        int N = A.length;
        for (int i=0; fibo(i)<=N+1; i++) fibo(i);

        ArrayList<Integer> fiboList = new ArrayList<>(fiboMap.values());
        Collections.reverse(fiboList);

        Queue<Point> queue = new LinkedList<>();
        boolean[] check = new boolean[N+1];

        queue.add(new Point(-1, 0)); // 시작점

        while(!queue.isEmpty()) {

            Point currentPoint = queue.poll();

            for (int fibo : fiboList) {
                int next = currentPoint.x + fibo;
                if (next == N) {
                    return currentPoint.y + 1;
                } else if (next < N && next >= 0) {
                    if (A[next] == 1 && !check[next]) {
                        check[next] = true;
                        Point point = new Point(next, currentPoint.y + 1);
                        queue.add(point);
                    }
                }
            }
        }

        return -1;
    }

    public int fibo(int num) {
        if (num == 0) return 0;
        if (num == 1) return 1;
        if (fiboMap.containsKey(num)) return fiboMap.get(num);
        fiboMap.put(num, fibo(num-1) + fibo(num-2));
        return fiboMap.get(num);
    }

    class Point {
        int x,y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }