[Codility] [Javascript] FrogJmp

Task description

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:

function solution(X, Y, 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.

 

---

 

📢 이번 문제는 시간 복잡도를 신경써야 했다.

처음엔 단순히 반복문을 사용해 구현했는데, time out이 걸려버렸다 😓

 

단순 그자체...

 

정확성은 100점이지만, 작업 점수 44점 & 퍼포먼스 0점...! 😭

 

 

---

 

시간 복잡도를 줄이기 위해 거리를 계산하는 공식을 떠올렸고,

X와 Y 사이의 거리를 D로 나눈만큼 점프한 후 아직 Y에 도착 못했다면 한 번 더 점프하도록 구현했다.

 

아주 단순한 풀이지만 훌륭한 개발자의 길은 멀고도 험하다.....

 

 

🌈 FrogJmp.js

/**
 * Count minimal number of jumps from position X to Y.
 * @param {*} X : 출발 지점
 * @param {*} Y : 도착 지점
 * @param {*} D : 점프 거리
 */
function solution(X, Y, D) {
    let answer = Math.floor((Y-X)/D); // X와 Y 사이의 거리를 D로 나눈만큼 점프
 
    // 아직 Y에 도착 못했다면 한 번 더 점프
    if ((Y-X) % D !== 0) {
        answer++;
    }
 
    return answer;
}

 

 

 

👩‍💻 풀어보기 👨‍💻 https://app.codility.com/programmers/lessons/3-time_complexity/frog_jmp/start/

Codility