[Codility] Lesson 3 FrogJmp 파이썬

문제풀이

정수X, D, Y가 주어졌을 때, X에 위치한 한 번에 D만큼 점프하는 개구리가 Y와 같거나 큰 거리만큼을 가는데 필요한 최소 점프수를 구하는 문제

단순히 X값이 Y보다 커질때까지 D를 더해주면 되나? 라고 생각하고 코드를 짰는데

def solution(X, Y, D):
    jump_count = 0

    while X < Y: # 현재 위치가 목표 지점에 닿을때까지 반복
        X = X + D
        jump_count += 1

    return jump_count

뭔가 분명 이렇게 쉬울리가 없다는 생각에 예외를 찾아보려고 생각해봤는데... X, Y, D 전부 양의 정수이고 Y값이 X값 보다 크다는 조건까지 전부 잘 명시되어 있어서 일단 제출해보았다.

그럼 그렇지... 생각해보니 성능보다 정확성을 요구했던 이전 문제들과는 달리 이 문제의 테마는 시간 복잡도다.

통과 못 한 케이스들 전부 시간 초과.

트러블 슈팅

O(n)에서는 시간 초과가 나는 것 같으니 시간복잡도를 O(log n)이나 O(1)으로 줄여야 한다.

최종 제출 코드

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import math

def solution(X, Y, D):

    jump_count = (Y - X) / D
    result = math.ceil(jump_count) # 결과값 올림
    
    return result

(최종위치 - 현재위치) / 이동거리 의 결과를 올림하면 Y에 도달하기 위한 최종 이동 횟수가 나온다. 시간복잡도는 O(1).