문제 개요
양수와 음수가 섞여 있는 정수 배열이 주어졌을 때, 배열의 요소들로 만들 수 있는 양수 부분 집합과 음수 부분 집합 사이의 차이를 최대화하는 것이 이번 문제의 목표입니다.
핵심 아이디어는 생각보다 간단합니다. (양수의 합) − (음수의 합)은 항상 최댓값이 됩니다. 음수를 빼는 것은 결국 그 절댓값을 더하는 것과 같기 때문입니다. 따라서 배열의 모든 음수를 양수로 바꾼 뒤 전체 요소를 더하면 원하는 결과를 얻을 수 있습니다.
예제 1
입력 − Arr[] = { -2, 0, -3, 8, 10, 12, -4 }
출력 − 두 부분 집합 간 최대 차이 − 39
설명 − 양수 부분 집합 {0, 8, 10, 12}의 합은 30입니다.
음수 부분 집합 {-2, -3, -4}의 합은 -9입니다.
따라서 최대 차이는 30 − (-9) = 39가 됩니다.
예제 2
입력 − Arr[] = { -5, -15, -3, -2, 10, 20, 15 }
출력 − 두 부분 집합 간 최대 차이 − 70
설명 − 양수 부분 집합 {10, 20, 15}의 합은 45입니다.
음수 부분 집합 {-5, -15, -3, -2}의 합은 -25입니다.
따라서 최대 차이는 45 − (-25) = 70이 됩니다.
접근 방식
아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.
- 양수와 음수 정수를 담고 있는 정수형 배열 Arr[]를 준비합니다.
- 함수 subsetDifference(int arr[], int n)은 양수 부분 집합과 음수 부분 집합 사이의 최대 차이를 계산합니다. 이 함수는 배열 자체와 배열의 크기 n, 두 개의 인자를 받습니다.
- 배열 전체 요소의 합을 저장할 변수 sum = 0을 선언합니다.
- 왼쪽부터 시작해 for 루프(i = 0; i < n; i++)로 배열의 각 요소를 순회합니다.
- 현재 요소가 음수(< 0)라면 -1을 곱해 양수로 변환합니다(arr[i] = arr[i] * -1).
- 각 요소를 sum에 누적해 더합니다.
- 구할 수 있는 최대 부분 집합 차이로서 sum을 반환합니다.
예제 코드
#include <stdio.h>
int subsetDifference(int arr[], int n){
int sum = 0;
for (int i = 0; i < n; i++){
if(arr[i]<0)
arr[i] = arr[i] * -1;
sum += arr[i];
}
return sum;
}
// 드라이버 코드
int main(){
int arr[] = { -1, 3, 5, 17, -32, 12 };
int n = 6;
printf("두 부분 집합 간 최대 차이 : %d", subsetDifference(arr, n));
return 0;
}
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 별도의 추가 공간 없이 제자리에서 동작합니다. 0은 부호가 없으므로 합에 영향을 주지 않습니다.
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
두 부분 집합 간 최대 차이 : 70