[codility] FrogJmp 문제

시간 복잡도를 중요하게 생각하고 풀어야 하는 문제이다.

처음 문제를 보고 for loop 가 생각했는데, 초기값과 증가하는 구문이 루프 앞과 바디로 들어가면서 결국 종료 조건을 보는 부분만 남게 되었다. 그래서 while로 바꾸었다.

1차로 만든 버전은 아래와 같이 되었다.

public int solveWithLoop(int X, int Y, int D) {
   int cp = X;
   int count = 0;
   while (cp < Y) {
      cp = cp + D;
      count++;
   }
   return count;
}

그런데 테스트를 돌려보니 실패가 난다.

시간복잡도는 선형이다.

시간이 오래 걸리는 것은 계산 제한 시간을 초과해 버리는 것이 문제이다.

그래서 계산을 하는 것으로 바꾸었더니 통과가 된다.

시간복잡도는 상수.

public int solveWithCalculate(int X, int Y, int D) {
   int count = (Y - X) / D;
   if (D * count + X == Y) {
      return count;
   }

   return count + 1;
}