(Python3) - LeetCode (Medium) : 3867. Sum of GCD of Formed Pairs

https://leetcode.com/problems/sum-of-gcd-of-formed-pairs

Sum of GCD of Formed Pairs - LeetCode

유클리드 gcd 구현해보고 자료구조와 정렬해보는 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

현재까지의 최댓값을 저장할 current_max_num, 정답 누적값을 저장할 sum, prefixGcd를 선언 후 적절히 초기화해줍ㅂ니다.

📔 풀이과정

📑 prefixGcd 구하기
1. nums의 원소를 순회하며 현 원소 num과 current_max_num과 비교해 더 큰 값이 있다면 갱신해줍니다.

2. num과 current_max_num의 gcd값을 구합니다. gcd를 구할 때는 시간 초과가 되지 않기 위해 O(logN)으로 구현되어야 합니다.

📑 prefixGcd 오름차순으로 정렬하기

📑 누적합 구하기
prefixGcd의 양옆에서 가운데로 순회하며 양끝마다 구한 gcd값을 sum에 누적해 더해줍니다.

📑 시간 복잡도

O(NlogN): pregixGcd길이의 절반만큼 순회하며 gcd를 O(logN)만에 구하기 때문입니다.

📑 공간 복잡도

O(N): n만큼의 길이 배열을 생성하기 때문입니다.

📔 정답 출력 | 반환

sum을 반환합니다.

---

📕 Code

📔 Python3

class Solution:
    def gcd(a:int, b:int) -> int:
        if b == 0:
            return a
        return gcd(b, a%b)

    def gcdSum(self, nums: list[int]) -> int:
        prefixGcd = []

        sum = 0

        current_max_num = nums[0]

        for num in nums:
            current_max_num = max(current_max_num, num)
            prefixGcd.append(gcd(num,current_max_num))
        prefixGcd.sort()

        prefix_gcd_len = len(prefixGcd)
        for i in range(prefix_gcd_len//2):
            sum += gcd(prefixGcd[i], prefixGcd[prefix_gcd_len-i-1])
        return sum

 

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.