Codility - ChocolatesByNumbers 문제풀이 - Henry's Algorithm

 

 

 

안녕하세요!ㅎㅎ

알고리즘을 공부하는 개발자 Henry입니다!

 

오늘은 제가 오랜만에 Codility 사이트에서 문제를 한번 풀어보았는데요,

Painless 난이도의 문제여서 비교적 쉽게 풀리나 싶었는데,

 

생각보다 시간이 걸렸던 것 같습니다.

 

처의 첫번째 시도는 아래와 같습니다!

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

def solution(N, M):
    # write your code in Python 3.6
    chocolates = [0]*N
    _current = 0
    while chocolates[_current] != 1:
        chocolates[_current] = 1
        _current = (_current+M)%N

    return sum(chocolates)
    pass

 

배열을 활용해서 정직하게 문제 그대로 풀려고 하였는데요,

이렇게 풀게 되면 정확도는 맞출 수 있었는지는 모르겠지만,

시간효율에 대해서는 Timeout으로 점수를 얻지 못했습니다..ㅠ!

 

이 문제는 산수로 풀 수 있는 문제입니다.

특별히 Codility에서는 이 문제를 유클리드 알고리즘으로 접근하도록

분류를 해놓았는데요,

 

아래는 제가 문제를 정확하게 다시 읽고 몇번의 시도 끝에 풀게 된 코드입니다.

 

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

def solution(N, M):
    # write your code in Python 3.6
    from math import gcd
    return N//gcd(M,N)

    pass

 

2줄이면 끝나는 문제이지요..?

 

때로는 생각나는 대로 무작정 덤비는 것보다,

산수와, 수식 등을 적용할 수 있는지 한번 더 고민해본 후에 문제를 풀어나가는 것도 좋은 방법일 것 같습니다.

 

그럼 오늘도 즐거운 코딩하세요!

 

 

아래는 제가 푼 문제 해설 영상이니 참고하시면 좋을 것 같습니다!ㅎㅎ

https://www.youtube.com/watch?v=7F7fICsnNOQ 

 

감사합니다!