1005. Maximize Sum Of Array After K Negations

출처: leetcode.com/problems/maximize-sum-of-array-after-k-negations/

분류: Greedy, Easy

---

접근방식

 k번 동안 배열에서 숫자를 하나 선택해 양수 음수 값을 바꿔야 합니다. k번 반복 이후 배열의 합이 가장 큰 경우를 찾는 문제입니다.

배열에서 음수가 있으면 모두 양수로 바꿔주고 음수를 모두 바꾸고도 k가 남아있다면 가장 최소인 숫자를 찾아서 그녀석을 한 번만 바꿔주면 됩니다. 방법 자체는 어렵지 않은데 생각해야 할 경우들이 조금 있어서 많이 틀렸습니다. 😭

해결방법

우선 음수를 모두 바꿔주기 위해 오름차순으로 정렬 후 

0번부터 다음 인덱스가 양수일 때까지 양수로 바꿔주고 인덱스를 증가시킵니다.

양수일 때가지 찾았는데, k가 아직 홀수번 남았다면 배열에서 최소값을 찾아 배열의 합에서 최소값을 2배만큼 빼줍니다.
(정렬해서 0번 인덱스를 음수로 바꿔주고 합해도 같습니다.)

func largestSumAfterKNegations(_ A: [Int], _ K: Int) -> Int {
    var orderedA = A.sorted(by: <)
    var index = 0
    for _ in 0..<K {
        if orderedA[index] < 0 {
            orderedA[index] *= -1
            if orderedA[index+1] < 0 {
                index += 1
            }
        } else if !orderedA.contains(0) {
            orderedA.sort(by: <)
            orderedA[0] *= -1
        }
    }

    return orderedA.reduce(0, +)
}

 

func largestSumAfterKNegations(_ A: [Int], _ K: Int) -> Int {
    var orderedA = A.sorted(by: <)
    var index = 0
    var k = K
    while k > 0 {
        if orderedA[index] < 0 {
            orderedA[index] *= -1
            if orderedA[index+1] < 0 {
                index += 1
            }
            k -= 1
        } else if !orderedA.contains(0) {
            k %= 2
            if k == 1 {
                let sumA = orderedA.reduce(0, +)
                return sumA - 2 * orderedA.min()!
            }
            break
        } else {
            break
        }
    }

    return orderedA.reduce(0, +)
}

 

배운점

쉬운 문제라고 제대로 풀지 못하면 결국 틀린 답이다. 실제 코테에서 이러면 망... 똑바로 풀자