[Codility] 4. FrogJmp

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–2021 by Codility Limited.

All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

 

몇번의 움직임으로 개구리가 목적지에 닿을 수 있는지 계산하는 문제이다.

 

출발지 - X

목적지 - Y

한번에 움직일 수 있는 거리 - D

 

언뜻 보기에는 X에 D를 계속 더해서 Y와 값이 같아지거나 넘어가면

D가 몇번 더해졌는지 count한 값을 return 하면 될 것 같지만

위 방법처럼 for문을 돌 경우,

정확성 면에서는 문제가 없지만 성능면에서 문제가 생길 것이다.

 

고로 이건 수학적인 접근이 필요한 문제다.

 

 

나는 이렇게 풀었다.

우선 목적지 Y에서 초기 시작값 X를 빼고

D로 나눈 몫을 quotient 라 하고,

D로 나눈 나머지를 remainder 라고 한다.

 

Y에서 X를 뺸 후 D로 나눈 나머지 remainder 가 0 이상인 경우,

quotient 만큼 움직였어도 remainder 만큼의 거리가 남은 것이기 때문에

quotient 에 1을 더해주고

그렇지 않은 경우 그대로 quotient 를 return 해주었다.

 

예외 상황으로

X와 Y가 같은 경우, 움직임 D에 상관없이 0을 return 하고

D가 1인 경우, Y에서 X를 뺀 값을 return 해 주었다.

 

// 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");

class Solution {
    public int solution(int X, int Y, int D) {
        // write your code in Java SE 8
        if(X == Y){
            return 0;
        }else if(D == 1){
            return Y - X;
        }
        
        int result = 0;

        int quotient = (Y-X)/D;
        int remainder = (Y-X)%D;

        if(remainder > 0){
            result = quotient + 1;
        }else{
            result = quotient;
        }

        return result;
    }
}

 

결과는 통과.

 

- 다른분들이 푼 방식들

예상대로 for문이 아닌 수식으로 풀어내는것이 맞았으며,

나는 Integer 값을 이용해 몫과 나머지를 생각한 반면

애초부터

소수점까지 나오게 double을 이용하여 나누고,

올림 처리 해버리는 방법이 있었다.

double jump = Y-X / (double) D;
return (int) Math.ceil(jump);

 

double을 알지만 Integer로 계산하는 방식만 생각났는데

여러 활용 방법이 있다는걸 계속 생각해야겠다.