1. 문제 소개

2169. Count Operations to Obtain Zero

2. 나의 풀이

간단하게는 문제의 규칙대로 큰 수에서 작은 수를 빼면 된다.
그러나 조금 더 간단하게 풀고 싶어 생각을 해봤다.
이 경우는 유클리드 호제법을 사용하면 몫과 나머지를 구하고 최대공약수를 구하는 시점까지의 몫을 정답에 더하면 된다고 생각했고, 다행히 정답이 맞았다.
시간복잡도는 $O(log\,max(num1, num2))$이다.

class Solution:
    def countOperations(self, num1: int, num2: int) -> int:
        if num1 == 0 or num2 == 0:        # 한쪽이 0이면 더 이상 연산 불필요
            return 0
                                               
        if num1 == num2:                  # 두 수가 같으면 한 번 빼면 바로 0
            return 1

        if num1 < num2:                   # 항상 num1 >= num2 유지
            num1, num2 = num2, num1

        ans = 0                           # 연산 횟수 누적
        while num2:                       # 유클리드 호제법 형태로 반복
            ans += num1 // num2           # num1에서 num2를 몇 번 뺄 수 있는지(몫) = 한번에 묶은 연산 수
            num1, num2 = num2, num1 % num2# 다음 상태: (작은 수, 나머지)
                                          # num2가 0이 되면 종료
        return ans                        # 총 연산 횟수 반환

3. 다른 풀이

푸는 방식은 동일한 한 줄 짜리 코드가 있었다.

class Solution:
    def countOperations(self, x: int, y: int) -> int:
        return 0 if y==0 else x//y+self.countOperations(y, x%y)

4. 결론

문제의 규칙대로 풀 경우 33~43ms 시간이 걸리지만, 유클리드 호제법을 사용하면 0ms이내로 풀 수 있다.
알고리즘의 중요성을 다시금 깨닫는다.