[Codility - Java] 3. Time Complexity - 1. FrogJmp

2023. 1. 31. 14:49Java/coding test



Count minimal number of jumps from position X to Y.

A small frog wants to get to the other side of the road.
The frog is currently located at position X and wants to get to a position greater than or equal to Y.
The small frog always jumps a fixed distance, D.

Count the minimal number of jumps that the small frog must perform to reach its target.

Write a function:

class Solution { public int solution(int X, int Y, int D); }

that, given three integers X, Y and D, returns the minimal number of jumps from position X to a position equal to or greater than Y.

For example, given:

X = 10
Y = 85
D = 30

the function should return 3, because the frog will be positioned as follows:

  • after the first jump, at position 10 + 30 = 40
  • after the second jump, at position 10 + 30 + 30 = 70
  • after the third jump, at position 10 + 30 + 30 + 30 = 100

Write an efficient algorithm for the following assumptions:

  • X, Y and D are integers within the range [1..1,000,000,000];
  • X ≤ Y.

개구리가 도로 반대편으로 가고 싶어한다.
현재 X 위치에 있다고 할 때, Y 위치로 가려고 한다. (이때, Y 위치를 넘어서도 된다.)
개구리는 항상 고정된 거리인 D만큼 점프한다.

몇번을 뛰어야 D에 도달하게 되는지 리턴하면 된다.

X <= Y
1 <= X, Y, D <= 1,000,000,000,000

static int flogJmp(int X, int Y, int D) {
    if(X == Y) return 0;
    if(X + D >= Y) return 1;
    return (int)Math.ceil((double)(Y - X) / D);


X와 Y가 같은 경우에는 0
X + D가 Y보다 클 경우에는 1
그 외의 경우에는 연산을 하면 되는데

거리 3을 2로 몇번이면 도달할 수 있느냐라고 할 때, 2번을 해야합니다.
즉, 소수의 올림을 활용하면 됩니다.

Math.ceil 함수는 double 자료형을 받는 함수이기 때문에 정확한 연산을 위해 분자 또는 분모 둘 중 하나를 double로 치환한 후 실행해야합니다.

그 후에는 int로 자료형을 변경해주면 끝