시간복잡도를 고려한 알고리즘

아래 문제는 코딜리티에서 제공하는 FlogJmp의 문제입니다🧑🏻‍💻

문제 제시

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.

문제 해결

import Foundation
import Glibc

public func solution(_ X : Int, _ Y : Int, _ D : Int) -> Int {
    let count = (Double(Y) - Double(X)) / Double(D)

    return Int(ceil(count))
}

사용된 개념

 - 소수점 올림

 - 사칙연산

문제 뒷담화

해당 문제는 문제 자체는 되게 간단하였다.

X에서 Y만큼 D씩 얼마나의 횟수를 통해 이동할 수 있는지를 묻는 문제였다.

처음에는 아래와 같이 while문을 사용해 구현해주었다.

import Foundation

public func solution(_ X : Int, _ Y : Int, _ D : Int) -> Int {
    var location = X
    var count = 0

    while location < Y {
        location += D
        count += 1
    }

    return count
}

그러나 해당 알고리즘으로는 시간 복잡도가 O(Y-X)가 걸려 D가 굉장히 적고 X와 Y사이 거리가 꽤 먼 테스트케이스의 경우는 시간초과로 통과하지 못하였다.

그래서 가장 단순히 생각한게 위와 같이 처음 X와 Y사이의 거리를 구하고 D(이동할 수 있는 거리)를 나눠 카운트 변수를 만들어주고

해당 변수를 소수점을 버리고 정수부를 1씩 올리는 올림 함수를 사용하여 Int값으로 리턴해주니 시간 복잡도가 항상 O(1)로 효율적인 알고리즘으로 개선되었다.

문제 자체는 굉장히 쉬웠지만 앞으로 알고리즘을 풀며 시간 복잡도를 꼭 고려해야하는걸 느꼈다.

[참고자료]

https://app.codility.com/c/run/trainingQPKF76-34Y/

Codility