문제 소개
정수로 이루어진 리스트 nums와 연산 횟수를 나타내는 값 k가 주어집니다. 여기서 '연산'이란 리스트에서 원소 하나를 선택해 부호를 반전시키는(양수→음수, 음수→양수) 동작을 의미합니다. 우리는 정확히 k번의 연산을 수행할 수 있으며, 그 결과로 만들 수 있는 최대 합을 구하는 것이 목표입니다.
예를 들어 입력이 다음과 같다고 가정해 보겠습니다.
nums = [2, 1, -6, -2], k = 3
-6, -2, 그리고 1의 부호를 각각 반전하면 리스트는 [2, -1, 6, 2]가 되며, 이때의 합은 9입니다. 따라서 출력은 9가 됩니다.
접근 방법: 그리디 알고리즘
이 문제는 그리디(Greedy) 방식으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음 두 가지입니다.
절댓값이 큰 음수부터 양수로 변환: 음수를 양수로 바꾸면 해당 값의 2배만큼 총합이 증가합니다. 따라서 리스트를 오름차순으로 정렬한 뒤, 앞쪽의 음수들부터 순서대로 반전하면서 남은 연산 횟수 k를 줄여 나갑니다.
남은 k가 홀수일 때의 손실 최소화: 모든 음수를 처리한 후에도 k가 남아 있다면, 남은 연산은 양수에 적용될 수밖에 없습니다. 같은 값을 짝수 번 반전하면 원래대로 돌아오므로, k가 홀수일 때만 문제가 됩니다. 이 경우 리스트에서 가장 작은 값(절댓값이 가장 작은 수)을 한 번만 반전하는 것이 손실을 최소화하는 방법이며, 결과적으로 전체 합에서 (최솟값 × 2)를 빼주면 됩니다.
해결 단계
n := nums의 길이로 설정
n이 0이면 0을 반환
nums를 오름차순으로 정렬
인덱스 0부터 n-1까지 반복하면서, nums[idx] < 0이고 k > 0이면 k를 1 감소시키고 nums[idx]의 부호를 반전
반복이 끝난 후 k가 홀수라면 (전체 합) − (2 × 최솟값)을 반환
k가 짝수라면 전체 합을 그대로 반환
구현 예제
아래 파이썬 코드를 통해 더 잘 이해해 보겠습니다.
def solve(nums, k):
n = len(nums)
if n == 0:
return 0
nums.sort()
for idx in range(n):
if nums[idx] < 0 and k > 0:
k -= 1
nums[idx] *= -1
if k & 1 == 1:
return sum(nums) - 2 * min(nums)
return sum(nums)
nums = [2, 1, -6, -2]
k = 3
print(solve(nums, k))
입력
[2, 1, -6, -2], 3
출력
9
동작 과정 살펴보기
예제 입력 [2, 1, -6, -2], k = 3에 위 코드를 적용하면 다음과 같이 진행됩니다.
정렬 후 리스트: [-6, -2, 1, 2]
-6을 반전 → k = 2, 리스트: [6, -2, 1, 2]
-2를 반전 → k = 1, 리스트: [6, 2, 1, 2]
나머지 원소는 양수이므로 반복 종료, k = 1 (홀수)
전체 합 11에서 최솟값 1의 2배인 2를 빼면 9 → 최종 출력: 9
복잡도 분석
정렬이 지배적인 연산이므로 시간 복잡도는 O(n log n)이며, 제자리 정렬을 사용하므로 추가 공간 복잡도는 O(1)입니다.