•
문제 링크 : leetcode.com
•
문제 설명 : 음수와 양수가 함께 존재하는 배열에서 k 번 동안 특정 요소의 부호를 바꿀 수 있다고 할때, 배열의 합을 가장 크게 만들 수 있는 경우의 수를 구한다.
•
풀이 방법
◦
가장 크게 합계를 만들기 위해서는 절대 값이 큰 음수를 1순위로 지워야했다.
▪
이를 위해 sorting을 통해 절대 값이 큰 음수를 먼저 부호를 바꿔주었다.
◦
이후 k가 남았다면, 가장 절대 값이 작은 요소에만 전부 사용하는 방식을 택하였다.
•
시간복잡도 :
•
성공 코드
class Solution:
def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
# 음수를 고려한 정렬을 위해 사용
nums.sort()
# 가장 작은 절대 값 구하기
minimum_abs = float("inf")
result = 0
# 가장 큰 합산을 만들기 위해, k의 남은 횟수만큼 절대 값이 큰 음수를 양수로 만든다.
for i in range(len(nums)):
# 음수 -> 양수
if k > 0 and nums[i] < 0:
nums[i] = nums[i] * -1
k -= 1
# k가 모든 음수를 양수로 만들어도 남을 수 있기 때문에, 가장 절대 값이 작은 수를 음수로 만들 것이다
# 이를 위해 절대 값이 가장 작은 요소를 순회하며 같이 확인한다.
minimum_abs = min(minimum_abs, abs(nums[i]))
# 합계 처리
result += nums[i]
# k가 짝수개로 남았다면, 동일 요소의 부호가 바뀌지 않는다.
# k가 홀수개로 남았다면, 결국에는 하나의 요소를 음수로 바꿔야하기 때문에 절대 값이 가장 작은 수를 음수로 만든 후 합산한다.
return result - (minimum_abs * 2) if k % 2 == 1 else result
Python
복사