[Codility] Lesson 3 : FrogJmp - JAVA

문제

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.
Copyright 2009–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

문제 해설

solution(int X, int Y, int D)에 입력되는 숫자 X, Y, D의 범위는 1 ~ 1,000,000,000이고,
X는 Y와 같거나 작다.

현재 X 위치에 있는 개구리가 Y 위치까지 가고싶어한다.
개구리가 한 번 점프를 뛸 때 D 만큼 이동하는데 Y 위치까지 가기 위해 최소 몇 번의 점프를 뛰는지 계산한다.

예를 들어 X = 10, Y = 85, D = 30이라고 했을 때

        첫 번째 점프를 뛰었을 때 10 + 30이므로 개구리는 40에 위치한다.
        두 번째 점프를 뛰었을 때는 10 + 30에서 30을 더 뛰었으므로 개구리는 70에 위치한다.
        세 번째 점프를 뛰었을 때는 10 + 30 + 30에서 30을 더 뛰었으므로 개구리는 100에 위치한다.

개구리는 10에서 85까지 가기 위해 최소 3번 점프를 하였으며, 이 때 점프한 횟수를 결과로 반환하면 된다.

 

풀이 - 1

class Solution {
    public int solution(int X, int Y, int D) {
        int remainDistance = Y-X;
        if(remainDistance == 0) return 0;
        int div = remainDistance / D;
        int remain = remainDistance % D;
        if(remain > 0) div += 1;
        return div;
    }
}

 

'풀이 -1'에 대한 회고

(이번 회고는 별로 쓸게 없겠는데...?)

 

문제만 보고 반복문으로 구현한 사람도 분명 있을 것이다.

하지만 굳이 반복문을 사용할 이유가 없다.

지금 위치에서 목적지까지 남은 거리를 먼저 계산하고, 남은 거리를 D(점프할 수 있는 거리)로 나누어

몇 번을 점프해야 하는지 쉽게 계산할 수 있다.

 

즉, X(10)에서 Y(85)까지 남은 거리는 75!

남은 거리(75)를 D(점프할 수 있는 거리)로 나누면 2!

대신 나머지가 15이기 때문에 한번 더 점프를 해줘야된다.

그렇게 작성한 코드가 '풀이 -1'이다.

 

반복문도 필요없거 사칙연산 하나만으로 쉽게 계산할 수 있으니 퍼포먼스도, 알고리즘 효율도 좋을 것이다.

 

다른 사람의 풀이

class Solution {
    public int solution(int X, int Y, int D) {
        if((Y-X) == 0) return 0;
        return (int) Math.ceil((Y - X) / (double) D);
    }
}

 

'다른 사람의 풀이'를 통한 회고

 

코드 길이도 짧고, 시간도 짧다.

역시 다른 사람들의 코드도 잘 봐야한다.

나는 Math를 사용할 생각을 안했네...

가독성도 좋고! 또 공부했다!