Number of Subarrays With GCD Equal to K

문제 번호, 이름: 2447. Number of Subarrays With GCD Equal to K

문제 링크: https://leetcode.com/problems/number-of-subarrays-with-gcd-equal-to-k/description/

날짜: 2024/06/02

상태: 완료

 

이 문제를 고른 이유

리트코드 랜덤픽

문제 보고 처음 든 생각

그냥 N^2 개의 subarray에 대해서 gcd 구하면 되지 않나? gcd 구하는 건 Time complexity가 어떻게 되지? 다 풀고 찾아봐야겠다 일단 대충 생각했을 땐 O(logM) 쯤 일 것 같다. M<=10^9 니까 대충 O(1)

풀이 v1

• 소요 시간 12분

그냥 N^2개의 subarray에 대해 gcd 를 구하면 gcd를 두 수에 대해서만 구하는 게 아니라 1~N개의 숫자에 대해 구하는거라 O(N^3) 풀이이다.

하지만 바로 다음 생각이 났는데, (a, b)의 gcd를 알고 있다면 (a, b, c)의 gcd는 처음부터 구하지 않고, gcd(gcd(a, b), c) 로 구할 수 있는 성질이 있다. 그러니까 앞에서부터 누적해서 gcd를 구하면 N^2번의 iteration에서 O(1) 시간에 gcd를 구할 수 있다. 최종적으로는 시간복잡도가 O(N^2)가 되어서 안전하다

 

class Solution:
    def get_gcd(self, bigger, smaller):
        if smaller == 0:
            return bigger
        
        return self.get_gcd(smaller, bigger % smaller)

    def subarrayGCD(self, nums: List[int], k: int) -> int:
        answer = 0
        len_nums = len(nums)

        for i in range(len_nums):
            gcd = None
            for j in range(i, len_nums):
                if i == j:
                    gcd = nums[i]
                else:
                    gcd = self.get_gcd(max(gcd, nums[j]), min(gcd, nums[j]))
                
                if gcd == k:
                    answer += 1
                elif gcd < k:
                    break
        
        return answer

 

메모리를 엄청나게 적게 쓰고 (상위 0%)

속도가 다소 느린? 코드라고 한다. 그래도 최적 코드와 비교했을 때 시간복잡도가 크게 차이나는 풀이는 아닌 것 같다

풀이 v2

• 소요 시간 -

# v2 없음

 

 

이 문제를 풀고 얻은 것

• gcd 구하는 함수의 시간복잡도는 위 코드처럼 유클리드 호제법을 썼을 때 O(logN) 이라고 한다. 느낌적인 느낌이 맞았지만 그래도 한 번 더 확신을 얻었다
• 충격적인 사실.. 파이썬에는 math.gcd() 내장 함수가 있다고 한다

메모

• 저번에 gcd 문제를 한 번 풀어놨어서 이번엔 get_gcd() 함수를 바로 짤 수 있었다