길이가 같은 두 개의 정수 배열이 주어졌을 때, 다음 식의 최댓값을 구하는 것이 목표입니다.
|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|
여기서 최댓값은 0 <= i, j < arr1.length 범위 내의 모든 인덱스 조합(i, j)에 대해 계산됩니다. 예를 들어 두 배열이 [1,2,3,4]와 [-1,4,5,6]으로 주어지면 결과는 13이 됩니다.
접근 방식: 절댓값 전개
이 문제를 효율적으로 풀기 위해서는 세 개의 절댓값을 수학적으로 전개하여 부호 조합별로 식을 재구성하는 것이 핵심입니다. 각 절댓값 항은 내부 값의 부호에 따라 덧셈 또는 뺄셈으로 바꿀 수 있으며, 그 결과 인덱스 i에 해당하는 항들과 인덱스 j에 해당하는 항들을 서로 분리할 수 있습니다.
부호 조합은 총 8가지이지만, 모든 부호를 동시에 뒤집으면 값이 같아지므로 실질적으로는 다음 4가지 경우만 확인하면 됩니다.
- arr1[k] − arr2[k] + k
- arr1[k] + arr2[k] + k
- arr1[k] − arr2[k] − k
- arr1[k] + arr2[k] − k
각 조합마다 배열 전체에서 (최댓값 − 최솟값)을 구하고, 네 값 중 가장 큰 값이 곧 정답이 됩니다.
알고리즘 단계
- 배열 v를 받아 최댓값과 최솟값의 차를 반환하는 getVal 메서드를 정의합니다.
- maxVal은 −∞(INT_MIN), minVal은 +∞(INT_MAX)로 초기화합니다.
- i를 0부터 v의 크기까지 순회하며, minVal에는 v[i]와 minVal 중 작은 값을, maxVal에는 v[i]와 maxVal 중 큰 값을 저장합니다.
- maxVal − minVal을 반환합니다.
- main 함수에서는 길이 4의 배열 ret을 생성합니다.
- n을 arr1의 크기로 설정한 뒤, i를 0부터 n−1까지 순회하며 ret[0]부터 ret[3]까지 위 네 가지 조합의 값을 차례로 저장합니다.
- ans를 −∞(INT_MIN)으로 초기화하고, i를 0부터 3까지 순회하며 ans = max(ans, getVal(ret[i]))로 갱신합니다.
- ans를 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int getVal(vector<int>& v){
int maxVal = INT_MIN;
int minVal = INT_MAX;
for(int i = 0; i < v.size(); i++){
minVal = min(v[i], minVal);
maxVal = max(v[i], maxVal);
}
return maxVal - minVal;
}
int maxAbsValExpr(vector<int>& arr1, vector<int>& arr2) {
vector<int> ret[4];
int n = arr1.size();
for(int i = 0; i < n; i++){
ret[0].push_back(arr1[i] - arr2[i] + i);
ret[1].push_back(arr1[i] + arr2[i] + i);
ret[2].push_back(arr1[i] - arr2[i] - i);
ret[3].push_back(arr1[i] + arr2[i] - i);
}
int ans = INT_MIN;
for(int i = 0; i < 4; i++){
ans = max(ans, getVal(ret[i]));
}
return ans;
}
};
main(){
vector<int> v1 = {1,2,3,4}, v2 = {-1, 4, 5, 6};
Solution ob;
cout << (ob.maxAbsValExpr(v1, v2));
}입력
[1,2,3,4] [-1,4,5,6]
출력
13
복잡도 분석
배열을 한 번씩만 순회하면 되므로 시간 복잡도는 O(n)이며, 네 개의 보조 배열을 사용하므로 공간 복잡도 역시 O(n)입니다. 모든 인덱스 쌍을 일일이 검사하는 브루트 포스 방식(O(n²))보다 훨씬 효율적인 풀이입니다.