[codility] Lesson 3 | FrogJmp - 파이썬(Python) | Time Complexity

https://app.codility.com/programmers/lessons/3-time_complexity/

3. Time Complexity lesson - Learn to Code - Codility

코딜리티 lesson 3 시간 복잡도에 관련된 문제를 풀었다.

x,y,d가 주어지고 개구리의 위치가 y와 같거나 클 때까지 x에 d를 몇번 더하면 되는지 푸는 문제이다.

---

시간 복잡도 문제이다 보니 확실히 효율성을 따져가면서 풀어야했다.

lesson3에 있는 세 문제 모두 생각없이 문제흐름대로 풀었다가 전부 시간 초과를 마주했었다 ㅎ

 

첫번째 풀이 - 실패

def solution(X,Y,D) :
    
    count = 0
    
    while X < Y :
        X = X+D
        count+=1
    
    return count

while문을 사용하여 간단하게 풀었으나 너무나도 당연하게 시간 초과가 되었다.

 

좀 더 효율적으로 풀 수 있는 방법을 검색해봤는데 나누기 연산 중에서 나눈 몫과 나머지를 함께 얻을 수 있는 divmod를 사용할 수 있다는 것을 알게 되었다.

 

두번째 시도 - 성공

def solution(X,Y,D):
    
    if X==Y :
        return 0

    dst = Y - X
    div, mod = divmod(dst, D)

    if not mod :
        return div
    else :
        return div+1

두번째 시도할 때 x와 y가 같을 때를 고려하지 않아서 case 부분에서도 실패했었다.

x와 y가 같으면 점프를 할 필요가 없으니 0을 반환하도록 해준 뒤에, y와 x의 차를 d로 나누어 몫과 나머지를 각각 반환했다.

나머지가 0인 경우에는 나누어 떨어지기 때문에 올림을 할 필요가 없으므로 몫인 div를 반환하도록 했다.

나머지가 0이 아닌 1~9라면 올림을 해주어야 하기 때문에 div에 1을 더해 반환했다.

---

해당 문제 풀이

GitHub - YOOHYOJEONG/algorithm_practice: 알고리즘 공부 및 코딩테스트 준비