[리트코드] 3867 - Sum of GCD of Formed Pairs

3867. Sum of GCD of Formed Pairs

Medium

---

You are given an integer array nums of length n.

Construct an array prefixGcd where for each index i:

• Let mxi = max(nums[0], nums[1], ..., nums[i]).
• prefixGcd[i] = gcd(nums[i], mxi).

After constructing prefixGcd:

• Sort prefixGcd in non-decreasing order.
• Form pairs by taking the smallest unpaired element and the largest unpaired element.
• Repeat this process until no more pairs can be formed.
• For each formed pair, compute the gcd of the two elements.
• If n is odd, the middle element in the prefixGcd array remains unpaired and should be ignored.

Return an integer denoting the sum of the GCD values of all formed pairs.

The term gcd(a, b) denotes the greatest common divisor of a and b.  

Example 1:

Example 2:

 

Constraints:

• 1 <= n == nums.length <= 105
• 1 <= nums[i] <= 10​​​​​​​9

분류

배열, 수학, 투 포인터, 정렬, 시뮬레이션, 정수론

---

문제 풀이

문제 분석

주어진 정수 배열 nums를 이용해 prefixGcd 배열을 구성하는 문제입니다.

• 입력: 정수 배열 nums (길이 n, 1 ≤ n ≤ 100,000, 원소 값 1 ~ 10^9)
• 출력: 조건에 따라 만들어진 쌍들의 GCD(최대공약수) 합 (정수)

과정 요약:

1. 각 인덱스 i까지의 최댓값 mx_i를 구하고, gcd(nums[i], mx_i)를 계산해 prefixGcd 배열을 만듭니다.
2. prefixGcd를 오름차순으로 정렬합니다.
3. 정렬된 배열에서 가장 작은 값과 가장 큰 값을 짝지어 GCD를 구하고, 그 다음 작은 값과 큰 값을 짝짓는 과정을 반복합니다(투 포인터 방식).
4. n이 홀수면 중간 값은 무시합니다.
5. 모든 쌍의 GCD 합을 반환합니다.

---

접근 방법

이 문제는 시뮬레이션과 투 포인터 기법을 그대로 구현하면 됩니다.

1. Prefix GCD 구성: 배열을 한 번 순회하며 현재까지의 최댓값(mx)을 유지합니다. 각 원소에 대해 gcd(현재 원소, mx)를 계산해 리스트에 저장합니다. 이 과정은 O(n) 시간에 가능합니다.
2. 정렬: 쌍을 "가장 작은 것 + 가장 큰 것" 순으로 맺기 위해 prefixGcd 배열을 정렬합니다. O(n log n) 시간이 소요됩니다.
3. 투 포인터로 쌍 처리: 정렬된 배열의 양 끝(left=0, right=n-1)에서 시작해 가운데로 모이며 GCD를 계산하고 누적합니다. left < right 조건으로 홀수 개수일 때 중간 원소가 자연스럽게 제외되도록 합니다. O(n) 시간에 처리됩니다.

자료구조는 단순한 리스트(prefixGcd)만 사용하면 충분하며, 파이썬의 math.gcd 함수를 활용해 최대공약수를 효율적으로 계산합니다.

---

구현 설명

1단계: Prefix GCD 배열 생성

• 변수 mx를 0으로 초기화하고 prefixGcd 빈 리스트를 준비합니다.
• nums를 순회하며 mx = max(mx, nums[i])로 현재까지의 최댓값을 갱신합니다.
• math.gcd(mx, nums[i])를 계산해 prefixGcd에 추가합니다.

2단계: 배열 정렬

• 생성된 prefixGcd 리스트를 sort() 메서드로 오름차순 정렬합니다.
• 이렇게 하면 가장 작은 값은 인덱스 0에, 가장 큰 값은 인덱스 n-1에 위치하게 됩니다.

3단계: 투 포인터로 쌍의 GCD 합 계산

• left = 0, right = n - 1로 양 끝 인덱스를 초기화하고 answer = 0으로 합계를 준비합니다.
• while left < right: 반복문을 실행합니다. (같아지면 중복/중간 원소이므로 중단)
• 반복문 안에서 math.gcd(prefixGcd[left], prefixGcd[right])를 계산해 answer에 더합니다.
• left는 1 증가시키고, right는 1 감소시켜 다음 쌍으로 이동합니다.
• 반복 종료 후 answer를 반환합니다.

---

⏱복잡도 분석

• 시간 복잡도: O(n log n)

  • prefixGcd 구성: 배열을 한 번 순회하므로 **O(n)**입니다. (math.gcd는 로그 시간이지만 상수로 간주)
  • 정렬: 파이썬의 Timsort 기준 **O(n log n)**입니다.
  • 투 포인터 순회: 배열을 한 번 훑으므로 **O(n)**입니다.
  • 전체적으로 정렬이 지배적이므로 **O(n log n)**입니다.

• 공간 복잡도: O(n)

  • prefixGcd 리스트를 저장하기 위해 입력 크기 n에 비례하는 추가 공간이 필요합니다.
  • 정렬은 제자리 정렬(in-place)이므로 추가 공간은 O(1) 또는 O(log n) 스택 공간 정도만 사용합니다.

---

핵심 포인트

1. Prefix Maximum 유지: 매번 0부터 i까지 최댓값을 찾는 O(n^2) 방식이 아닌, 변수 하나(mx)로 현재까지의 최댓값을 갱신하며 O(1)에 구하는 것이 핵심입니다.
2. 정렬 후 투 포인터: "최소값과 최대값을 짝짓는다"는 조건은 정렬 후 양 끝에서 가운데로 포인터를 이동시키는 투 포인터 패턴으로 아주 간단히 구현됩니다.
3. 홀수 길이 처리: while left < right 조건을 사용하면 left == right가 되는 순간(가운데 원소) 루프가 종료되므로, 별도의 분기 처리 없이 중간 원소를 자연스럽게 무시할 수 있습니다.

풀이 코드

import math

class Solution:
    def gcdSum(self, nums: list[int]) -> int:
        n = len(nums)
        mx = 0
        prefixGcd = []
        for i in range(n):
            mx = max(mx, nums[i])
            prefixGcd.append(math.gcd(mx,nums[i]))

        left = 0
        right = n - 1
        answer = 0
        prefixGcd.sort()
        while left < right:
            answer += math.gcd(prefixGcd[left], prefixGcd[right])
            left += 1
            right -= 1

        return answer