leetcode - Maximize Sum Of Array After K Negations

 

주어진 A 배열에서 K 번만큼 부호를 변경하여 최대 sumation을 만드는 문제입니다.

(단, 부호는 동일 값을 중복하여 해도됩니다.)

 

저는 아래와 같이 풀었습니다.

class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        for i in range(K):
            if K == 0:
                break
            min_val = min(A)
            index = A.index(min_val)
            if min_val < 0:
                K -= 1
                A[index] = -min_val
            elif (K % 2) == 0:
                break
            else:
                K -= 1
                A[index] = -min_val
        return sum(A)

 

1. 배열에서 최솟값과 인덱스를 구해옵니다.

2. 음수라면 양수로 변경하여 배열의 값을 변경 및 K도 1 감소시킵니다.

3. 최솟값이 음수가 아니지만 K번이 짝수라면 현재 상태가 sumation 시 최대이기 때문에 연산을 멈춥니다.

4. 최솟값이 양수이고, K번도 홀수라면 그나마 작은 최솟값을 음수로 변경합니다.

 

감사합니다.