[Swift] Codility Lesson 3 - 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:

public func solution(_ X : Int, _ Y : Int, _ D : Int) -> Int

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.

 

링크

FrogJmp coding task - Learn to Code - Codility

 

문제 분석

• 현재 개구리의 위치 X에서 Y이상까지 가기 위해 몇 번을 움직여야 하는지 구하는 문제다.
• 개구리가 한 번에 뛸 수 있는 거리는 D만큼이다.

ex) X: 10, Y: 85, D: 30

1. 10 + 30 = 40
2. 40 + 30 = 70
3. 70 + 30 = 100

3번의 점프로 100까지 갈 수 있다 (>= 85)

 

해결방안

1. 가고 싶은 위치에서 현재 위치를 빼면 거리를 구할 수 있다.
2. 구한 거리를 한 번에 움직일 수 있는 거리로 나누면 이동하는데 걸리는 횟수를 구할 수 있다.
3. 계산한 이동 횟수만큼 이동했을 때, 가고 싶은 위치에 도착하지 못했다면 1을 더해준다.

count = (Y-X)/D

// 가고 싶은 위치에 도착하지 못한 경우
만약 (Y-X)% D 가 0이 아니라면 {
    count = count + 1
}

 

Solution

public func solution(_ X : Int, _ Y : Int, _ D : Int) -> Int {
    return (Y-X)%D == 0 ? (Y-X)/D : ((Y-X)/D)+1
}

• 시간 복잡도: O(1)