문제 소개
정수 배열 A가 주어졌을 때, 다음과 같은 방식으로 배열을 수정해야 합니다.
인덱스 i를 하나 선택해 A[i]를 -A[i]로 바꾸는 연산을 총 K번 수행할 수 있습니다. 모든 연산을 마친 뒤 만들 수 있는 배열 합의 최댓값을 구하는 것이 이 문제의 목표입니다.
예를 들어 A = [4, 2, 3]이고 K = 1이라면, 인덱스 1을 선택해 배열을 [4, -2, 3]으로 만들 수 있습니다. 이때 배열의 합은 5가 되며, 이것이 가능한 최댓값입니다.
문제 해결 접근법
이 문제는 그리디(Greedy) 알고리즘으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 음수는 우선적으로 뒤집는다: 음수를 양수로 바꾸면 합이 반드시 증가하므로, 절댓값이 큰 음수부터 차례로 뒤집는 것이 유리합니다.
- 남은 K가 짝수라면: 같은 원소를 두 번 뒤집으면 원래 값으로 되돌아오므로, 합에 손실 없이 K를 소진할 수 있습니다. 따라서 현재 합을 그대로 반환합니다.
- 남은 K가 홀수라면: 어느 한 원소를 홀수 번 뒤집어야 하므로, 절댓값이 가장 작은 원소를 선택하는 것이 최선입니다. 이때 합은 2 × (그 원소의 값)만큼 감소합니다.
알고리즘 단계
- 배열 A를 오름차순으로 정렬합니다.
- i를 0부터 A의 길이 - 1까지 순회하며, A[i] < 0이면 A[i] := -A[i]로 바꾸고 k를 1 감소시킵니다.
- k가 0이 되면 반복문을 종료합니다.
- 반복이 끝난 후 k가 홀수이면, 가장 작은 원소 sp를 찾아 (배열 전체의 합) - (2 × sp)를 반환합니다.
- k가 짝수이면 배열 전체의 합을 그대로 반환합니다.
Python 구현 예제
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
class Solution(object):
def largestSumAfterKNegations(self, A, K):
A.sort()
# 음수를 양수로 뒤집기
for i in range(len(A)):
if A[i] < 0:
A[i] = -A[i]
K -= 1
if K == 0:
break
# 남은 K가 홀수라면 가장 작은 원소를 한 번 더 뒤집기
if K % 2:
smallest_positive = A[0]
for i in range(1, len(A)):
if A[i] >= 0:
smallest_positive = min(smallest_positive, A[i])
return sum(A) - (2 * smallest_positive)
else:
return sum(A)
ob1 = Solution()
print(ob1.largestSumAfterKNegations([3, -1, 0, 2], 3))
입력
[3, -1, 0, 2]
3
출력
6
동작 과정 살펴보기
입력 배열 [3, -1, 0, 2]를 정렬하면 [-1, 0, 2, 3]이 됩니다. 첫 번째 원소 -1을 뒤집으면 배열은 [1, 0, 2, 3]이 되고 K는 2로 줄어듭니다. 남은 K가 짝수이므로 추가 손실 없이 합을 계산할 수 있으며, 최종 결과는 1 + 0 + 2 + 3 = 6입니다.
복잡도 분석
배열 정렬에 O(n log n)의 시간이 소요되고, 이후의 배열 순회는 O(n)이므로 전체 시간 복잡도는 O(n log n)입니다. 제자리 정렬을 사용하므로 추가 공간 복잡도는 O(1) 수준입니다.