[분석] Codility - FrogJmp - Javascript

Codility 연습문제 > FrogJmp > Javascript
위치 X에서 Y 로의 최소 점프 수를 계산합니다.

실제 문제의 저작권은 Codility 에 있으므로 전체 문제의 내용은 Codility 페이지를 방문해 확인하세요.

[문제 및 조건]

개구리가 길 건너편으로 가고 싶습니다. 개구리의 현재 위치 X, 목표 지점 Y, 개구리의 고정 점프 거리인 D가 주어질 때 개구리가 목표에 도달하기 위해 수행햐야하는 최소 점프 수를 구하세요.

1. 개구리의 현재 위치 X
2. 개구리의 목표 위치 Y (Y 또는 Y보다 크 위치에 도달 가능)
3. 개구리의 고정 점프 거리 D
4. X, Y, D 가 주어지면 X에서 Y보다 크거나 같은 위치로 갈 수 있는 최소 점프 수를 반한하라
   
   

[분석]

1. 개구리는 일정 점프 거리를 통해 Y에 도달하거나 Y 보다 큰 수의 위치로 도달해야 한다.
2. 개굴리의 고정 점프 거리를 이용해 이동했을 때, 최소로 이동할 수 있는 점프 횟수를 반한해야한다.
3. X, Y, D 는 1 ~ 1,000,000,000 범위 내의 정수이다.
4. 초기 값은 X <= Y 범위를 갖는다.

[풀이]

1. 현재 위치 X 와 점프 거리 D를 합산 (점프 횟수)를 이용해 X + D >= Y 인 경우의 수를 구한다.
2. 개구리의 X 위치값과 Y의 같을 수 있다. (점프 횟수 0)
3. X 와 Y의 차이값을 기준으로 점프 거리를 나누 횟수를 구한다.
4. 몫과 나머지의 값을 통해 점프 횟수를 구한다.
5. 결과값은 Y와 가장 근접한 값을 기준으로 점프 횟수를 반환하면 된다.
6. 결과값 뿐만아니라 성능을 측정하는 문제로, 불필요한 2중 반복문을 피해야합니다.

function solution(X, Y, D) {
  // 실제 남은 거리를 계산한다. (X <= Y)
  const distance = Y - X; 

  // 거리가 0 이 아니라면 점프 횟수를 구한다.
  if (distance > 0) {
    // 소수점 버림을 통해 점프 횟수 정수값을 구한다. 
    const jumpCount = Math.floor(distance / D);
    
    // 나머지 값이 있다면 Y지점에 도달하지 못했다는 의미이다. 
    // 그래서 +1 을 통해 목표지점 도달시 점프 횟수를 보정한다.
    return distance % D > 0 ? jumpCount + 1 : jumpCount;
  }

  // 기본 점프 횟수는 0 이다.
  return 0;
}

[마치며]

FrogJmp 문제는 for 문을 통해 D 값을 증가시키면서 Y 근삿값을 비교해 최소 점프 횟수를 구할 수도 있습니다. 성능을 생각하지 않는다면 계속해서 점프 횟수를 증가시켜 가장 작은 값을 비교해 답을 반환하는 것도 답이 될 수 있겠지만, for 반복문을 사용하지 않고 단순히 거리와 나머지 값만을 통해 최소 점프 횟수를 구하는 것이 문제의 핵심인듯 합니다. 즉, 시간 복잡도를 증가시키지 않고 최소한의 연산을 통해 값을 구할 수 있는지를 평가하는 워밍업 문제로 보입니다.