LeetCode | Easy | 1005. Maximize Sum Of Array After K Negations

LeetCode | Easy | 1005. Maximize Sum Of Array After K Negations

Problems

• 📘 Src: LeetCode
• 🗂️ Cat: Greedy

Description

Given an integer array nums and an integer k, modify the array in the following way:

• Choose an index i and replace nums[i] with -nums[i].
• You should apply this process exactly k times. You may choose the same index i multiple times.

Return the largest possible sum of the array after modifying it in this way.

Constraints

• 1 <= nums.length <= 10^4
• -100 <= nums[i] <= 100
• 1 <= k <= 10^4

Examples

nums	k	Output
[4,2,3]	1	5
[3,-1,0,2]	3	6
[2,-3,-1,5,-4]	2	13

Solutions

• ⏳ TC: O(n log n)
• 💾 SC: O(1)

import java.util.*;

class Solution {

    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);  // 배열을 오름차순으로 정렬
        
        // 가장 작은 수부터 순차적으로 k번 부호를 바꿈
        for (int i = 0; i < nums.length && k > 0; i++) {
            if (nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        
        // 부호를 바꿀 수 있는 기회가 남아있다면, 가장 작은 값을 다시 부호를 바꿈
        if (k % 2 == 1) {
            Arrays.sort(nums);
            nums[0] = -nums[0];
        }
        
        // 배열의 합을 계산
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        
        return sum;
    }
}

Approaches

이 문제는 주어진 배열 nums에서 k번의 부호 변경을 통해 배열의 합을 최대화하는 문제입니다. 그리디 알고리즘을 사용하여 접근합니다.

• 배열 정렬: 배열을 오름차순으로 정렬하여 가장 작은 값부터 순차적으로 부호를 변경합니다.
• 부호 변경: k번의 기회를 사용하여 음수 값을 양수로 바꿉니다. 음수 값을 양수로 바꾸면 배열의 합이 증가하기 때문입니다.
• 재정렬 및 추가 변경: 모든 음수 값을 양수로 바꾼 후에도 k가 남아있다면, 가장 작은 값을 다시 부호를 바꿔서 합을 최대화합니다. 이 경우, k가 부호가 변경되는 홀수일 때만 추가로 한 번 부호를 변경합니다.
• 최종 합 계산: 배열의 모든 요소를 합산하여 최종 결과를 반환합니다.

이 알고리즘의 시간 복잡도는 배열을 정렬하는 데 O(n log n), 배열을 순회하며 합을 계산하는 데 O(n)이므로 전체 시간 복잡도는 O(n log n)입니다. 공간 복잡도는 추가적인 공간 사용 없이 입력 배열을 직접 수정하므로 O(1)입니다.

Attempts

처음에는 가장 작은 값을 반복적으로 양수로 바꾸는 방식으로 접근했습니다. 이를 구현한 코드는 아래와 같습니다:

import java.util.*;

class Solution {

    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        for (int i = 0; i < k; i++) {
            if (nums[0] == 0) break; // 0을 만나면 더 이상 변경하지 않음
            if (nums[0] < 0) { // 음수 값을 양수로 바꿈
                nums[0] *= -1;
                Arrays.sort(nums); // 배열 재정렬
            } else { // 양수 값일 경우 부호만 바꿈
                nums[0] *= -1;
            }
        }
        
        int sum = 0;
        for (int num : nums) {
            sum += num; // 배열의 합 계산
        }
        return sum;
    }
}

이 접근 방식은 다음과 같은 문제점이 있었습니다:

• 배열을 반복적으로 정렬해야 하므로 시간 복잡도가 높아집니다.
• 배열을 계속 정렬하는 과정에서 불필요한 연산이 발생합니다.

최적화된 알고리즘은 가장 작은 값을 처리하는 방식으로, 배열을 한 번 정렬한 후 k번 반복하면서 가장 작은 값을 양수로 바꾸고 배열을 다시 정렬하는 방식을 사용합니다. 이를 통해 시간 복잡도를 줄이고 효율적인 처리가 가능합니다.