이 문제에서는 n개의 정수로 이루어진 배열이 주어지며, 우리의 목표는 |arr[i] - arr[j]| + |i - j| 식의 최댓값을 찾는 프로그램을 작성하는 것입니다.
문제 이해를 위한 예시
입력: array = {4, 1, 2}
출력: 4
설명:
|arr[0] - arr[1]| + |0-1| = |4-1| + |-1| = 3 + 1 = 4
|arr[0] - arr[2]| + |0-2| = |4-2| + |-2| = 2 + 2 = 4
|arr[1] - arr[2]| + |1-2| = |1-2| + |1-2| = 1 + 1 = 2
해결 방법 1: 브루트 포스 (Brute Force)
가장 단순한 접근 방식은 브루트 포스 기법입니다. 두 개의 반복문을 사용하여 모든 인덱스 쌍 (i, j)에 대해 값을 계산하고 그중 최댓값을 찾는 방법입니다.
하지만 이 방식은 시간 복잡도가 O(n²)으로 비효율적입니다. 더 효율적인 방법은 절댓값 함수의 성질을 활용하는 것입니다.
해결 방법 2: 수학적 최적화
절댓값은 부호 조합에 따라 다음과 같이 전개할 수 있습니다. 주어진 식을 분해해 보면,
arr[i] - arr[j] + i - j = (arr[i] + i) - (arr[j] + j)
arr[i] - arr[j] - i + j = (arr[i] - i) - (arr[j] - j)
-arr[i] + arr[j] + i - j = -{(arr[i] - i) - (arr[j] - j)}
-arr[i] + arr[j] - i + j = -{(arr[i] + i) - (arr[j] + j)}
위 네 가지 경우를 살펴보면, 첫 번째와 네 번째가 동일하고 두 번째와 세 번째가 동일함을 알 수 있습니다. 이 성질을 활용하면 두 개의 배열을 만들어 문제를 단순화할 수 있습니다.
- array1: arr[i] + i 값들을 저장
- array2: arr[i] - i 값들을 저장
따라서 최종 답은 다음 두 값 중 더 큰 값이 됩니다.
max((max(array1) - min(array1)), (max(array2) - min(array2)))
이 방법은 배열을 한 번씩만 순회하면 되므로 시간 복잡도 O(n), 공간 복잡도 O(n)으로 효율적입니다.
구현 예제
위 해결 방법을 구현한 C++ 프로그램입니다.
#include<iostream>
using namespace std;
int maxDiff(int arr[], int n) {
int ans = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
ans = max(ans, abs(arr[i] - arr[j]) + abs(i - j));
return ans;
}
int main() {
int array[] = { 5, 7, 1, 2 };
int n = sizeof(array) / sizeof(array[0]);
cout<<"|arr[i] - arr[j]| + |i-j|의 최댓값은 "<<maxDiff(array, n);
return 0;
}
출력 결과
|arr[i] - arr[j]| + |i-j|의 최댓값은 7
입력 배열 {5, 7, 1, 2}에 대해 프로그램은 모든 쌍을 비교하여 최댓값인 7을 정확히 출력합니다. 실제 대규모 입력에서는 앞서 설명한 최적화된 방법(O(n))을 적용하면 훨씬 빠른 실행 속도를 얻을 수 있습니다.