Codility Java FibFrog

문제

Link

코드

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Queue;
import java.util.LinkedList;

class Solution {
  private final Map<Integer, Integer> fibonacciMap = new HashMap<>();
  public int solution(int[] A) {
    for (int idx = 0; getFibonacciData(idx) <= A.length + 1; idx++) {
      getFibonacciData(idx);
    }
    List<Integer> fibonacciList = new ArrayList<>(fibonacciMap.values());
    Collections.reverse(fibonacciList);

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

    queue.add(new Point(-1, 0)); // Starting point.

    while (!queue.isEmpty()) {
      Point currentPoint = queue.poll();
      for (int fibonacci : fibonacciList) {
        int next = currentPoint.getPosition() + fibonacci;
        if (next == A.length) {
          return currentPoint.getJump() + 1;
        } else if (next < A.length && next >= 0) {
          if (A[next] == 1 && !check[next]) {
            check[next] = true;
            queue.add(new Point(next, currentPoint.getJump() + 1));
          }
        }
      }
    }
    return -1;
  }
  private int getFibonacciData(int num) {
    if (num <= 1) {
      return num;
    }
    if (fibonacciMap.containsKey(num)) {
      return fibonacciMap.get(num);
    } else {
      int temp = getFibonacciData(num - 2) + getFibonacciData(num - 1);
      fibonacciMap.put(num, temp);
      return temp;
    }
  }
}
class Point {
  private int position;
  private int jump;
  public Point(int position, int jump) {
    this.position = position;
    this.jump = jump;
  }
  public int getPosition() {
    return this.position;
  }
  public int getJump() {
    return this.jump;
  }
}

설명

1. 주어진 배열 A의 크기 + 1만큼 피보나치¹ 수열을 생성한다.
   • 피보나치 수열은 0, 1, 1, 2, …로 시작하지만, 불필요한 0과 첫 1은 제외하고 구성한다.(개구리가 점프하는 거리가 중복되는 것은 의미가 없다.)
2. 구한 피보나치 수열을 역순으로 변수 fibonacciList에 저장한다.
   • 개구리가 점프하여 이동하는 거리를 정방향이 아니라 역방향으로 계산하기 위함이다.
3. 개구리의 점프 횟수와 현재 위치를 저장하는 Point를 선입선출로 저장하는 변수 queue를 지정하여 초기 값을 넣어준다.
   • 초기값은 위치가 -1이고, 점프 횟수는 0으로 설정한다.
4. 개구리가 점프하여 닿을 수 있는 위치를 확인하는 변수 check 배열을 추가하여 점프를 통해 닿을 수 있는 위치를 저장해둔다.
5. 변수 queue의 값이 없을 때 까지 반복하여 개구리가 점프하여 이동할 수 있는지를 검증한다.
   • 역순으로 정렬한 피보나치 수열을 기반으로 반복하여, 개구리가 점프하여 이동할 수 있는지를 확인한다.
     • 만일 개구리의 현재 위치와 피보나치 수열 값의 합이 주어진 배열 A의 크기와 같으면 해당 거리만큼 개구리가 점프하면 강을 건널 수 있으므로, 기존 점프 횟수에 1을 증가하여 주어진 문제의 결과로 반환한다.
     • 혹은 개구리의 현재 위치와 피보나치 수열 값의 합이 주어진 배열 A의 크기보다 작고 0보다 클 경우 아래의 세부적인 검증을 하고, 그렇지 않은 경우 다음 피보나치 값으로 위의 반복을 계속 수행한다.
     • 해당 위치가 점프를 통해 밟을 수 있는 잎이 있으며 아직 밟지 않았다면, 해당 위치를 변수 check 배열에 true로, 새로운 Point를 생성하여 변수 queue에 추가한 후 해당 위치부터 맨 위의 반복을 다시 수행한다.
6. 만일 반복문이 정상적으로 종료되면, 개구리가 강 반대편에 도달 할 수 없다는 의미이므로 -1을 주어진 문제의 결과로 반환한다.

결과

Link

소스

Sample Code는 여기에서 확인 가능합니다.

Reference

1. Wiki-Fibonacci_Numbers ↩