[ Codility 코딜리티 ] Lesson 3 FrogJmp Python파이썬 풀이

 

//문제 요약

 

개구리가 길을 건너고자 한다.

이 개구리는 지금 X위치에 있고

한번 점프할 때 마다 D 만큼 이동할 수 있는데

Y 보다 크거나 같은 지점까지 갈 수 있는

최소 점프 횟수는 얼마인가?

 

 

// 풀이

 

이 문제는 while문 같은게 바로 떠오르는 아주 간단한 문제다.

하지만 X로 부터 Y 가 아주 멀고 D가 아주 작은 경우에는

while로 돌릴경우 시간 복잡도가 올라갈 수 있다.

따라서 X, Y 사이의 거리를 먼저 구하고

D로 나누어 주는 방식으로 루프를 피해서

간단히 계산할 수 있다.

 

while의 경우 O(n)이 걸릴 것으로 예상되고

나눗셈의 경우 O(1)이 걸릴 것으로 예상되므로

나눗셈을 선택하는 것이 옳다.

 

 

코드를 먼저 보자.

 

def solution(X, Y, D):
    # write your code in Python 3.6
    between = Y - X
    if not between:
        return 0

    div, mod = divmod(between,D)
    if not mod: # equal to
        return div
    else: # greater than
        return div +1

 

divmod() 함수는 파이썬의 내장함수로

플랫폼에 상관없이 쓸 수 있다.

 

div, mod = div,mod(a, b)

풀이하자면

a를 b 로 나누었을때

몫을 div, 나머지를 mod로 반환하는 함수이다.

 

이 함수가 a/b 와 다른점은

a/b의 경우 나머지가 생기면 소숫점 아래로 표현되지만

divmod()의 경우는 나머지를 그대로 알려준다는 것이다.

 

예를 들어 4/3 의 경우 1.33333... 으로

몫은 1 나머지는 0.3333... 이 되지만

div, mod = divmod(4, 3) 은

div = 1, mod = 1 이렇게 나타난다.

 

위의 풀이에서 mod가 0인 경우

딱 맞아 떨어지는 지점이므로 더 뛸 필요가 없지만

mod의 값이 있는 경우 1번을 더 뛰어야 Y를 넘어가기 때문에

div에 1을 더해주어야 한다.

 

 

코딜리티는 매우 다양한 입력값을 준비하므로

이 조건을 잘 보아야한다.

 

efficient algorithm 이므로

정확도가 같으면 더 효율적인 알고리즘을 써야한다.

 

또 D가 0인 경우 (개구리가 뛰지 않는 경우)

divmod()함수를 쓸 수 없는데

이러한 경우가 포함되어 있지 않으므로

예외처리를 해줄 필요가 없다.