[리트코드 3727] 제곱의 교대 합 최댓값 — 절댓값 정렬 후 큰 값은 더하고 작은 값은 뺀다

원제: Maximum Alternating Sum of Squares

문제 요약

정수 배열 nums의 원소를 임의의 순서로 재배치했을 때, 제곱값을 +,-,+,-,... 부호로 더한 교대 합의 최댓값을 구한다. 원소 자체의 부호와 관계없이 제곱값은 음수가 아니므로, 더하는 자리에 큰 제곱값을 배치하는 것이 유리하다.

조건과 입출력

1 <= nums.length <= 10^5이고 -4 * 10^4 <= nums[i] <= 4 * 10^4이다. 배열의 원소는 임의의 순서로 재배치할 수 있으며, 결과는 정수로 반환한다. 점수는 0번 인덱스에서 시작해 짝수 인덱스의 제곱은 더하고 홀수 인덱스의 제곱은 뺀다.

예제와 문제 자료

예제 1: nums = [1,2,3]이면 출력은 12이다. [2,1,3]의 점수는 2^2 - 1^2 + 3^2 = 12이다. 예제 2: nums = [1,-1,2,-2,3,-3]이면 출력은 16이다. 제시된 재배열 [-3,-1,-2,1,3,2]의 점수는 9 - 1 + 4 - 1 + 9 - 4 = 16이다.

풀이 아이디어

nums[i] ** 2는 abs(nums[i]) ** 2와 같으므로, 어떤 원소를 더하는 칸에 둘지는 절댓값의 크기로 결정된다. 더하는 칸의 제곱값을 크게 하고 빼는 칸의 제곱값을 작게 해야 합이 커진다. 제출 코드는 nums.sort(key = lambda x:abs(x))로 절댓값 오름차순 정렬한 뒤, 더하는 칸에는 뒤에서부터 큰 원소를, 빼는 칸에는 앞에서부터 작은 원소를 배정한다. 따라서 가능한 배치 중 큰 제곱값이 더해지고 작은 제곱값이 빠지는 구성이 된다.

코드의 핵심

answer는 현재까지 계산한 교대 합이다. 반복문에서 i % 2 == 0이면 더하는 칸이므로 nums[n-1-(i//2)] ** 2를 더한다. 인덱스가 정렬 배열의 끝에서 시작해 왼쪽으로 이동하므로 큰 절댓값부터 사용한다. 홀수 i에서는 nums[i//2] ** 2를 빼며, 정렬 배열의 앞에서부터 작은 절댓값을 사용한다.

예제 1의 코드 추적: 정렬 결과는 [1,2,3], n = 3이다. i=0에서 3^2를 더해 answer=9, i=1에서 1^2를 빼 answer=8, i=2에서 2^2를 더해 answer=12를 반환한다. 예제 2는 절댓값 기준 정렬 후 양수·음수와 관계없이 제곱값만 반영되며, 더하는 칸에 제곱값 9, 4, 9, 빼는 칸에 1, 1, 4가 배정되어 16이 된다.

제출 코드

class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        nums.sort(key = lambda x:abs(x))
        
        n = len(nums)
        answer = 0

        for i in range(n):
            if i % 2 == 0:
                answer += nums[n-1-(i//2)] ** 2

            else:
                answer -= nums[i//2] ** 2

        return answer

복잡도

n = len(nums)라 할 때 정렬은 O(n log n), 이후 한 번 순회하므로 전체 시간 복잡도는 O(n log n)이다. 정렬된 nums를 결과 계산에 사용하며, Python의 정렬 과정에 필요한 보조 공간은 최악의 경우 O(n)이다. 별도의 결과 배열은 만들지 않고 정수 answer만 저장한다.

복습 포인트

정렬 기준과 계산 대상은 모두 원소의 절댓값에 따른 제곱값이다. 따라서 음수 원소도 제곱한 뒤에는 양수처럼 더하거나 뺀다. 원소 수가 홀수이면 더하는 칸이 하나 더 많으며, 코드의 짝수 인덱스 분기가 그 남는 칸도 처리한다.

출처

문제 원문