문제 설명
배열 arr[]가 주어졌을 때, i ≠ j 조건을 만족하면서 (arr[i] – i) – (arr[j] – j)의 최댓값을 구하는 문제입니다. 여기서 i와 j는 0부터 n-1 사이의 값을 가지며, n은 입력 배열 arr[]의 크기입니다.
예를 들어 입력 배열이 {7, 5, 10, 2, 3}이라면 다음과 같이 최댓값 9를 얻을 수 있습니다.
(요소 10 – 인덱스 2) - (요소 2 – 인덱스 3)
(10 – 2) – (2 – 3) = 8 – (-1) = 9
알고리즘 접근 방식
이 문제의 핵심은 주어진 식을 분해하는 것입니다. (arr[i] – i) – (arr[j] – j)는 결국 "(arr[i] – i) 값 중 가장 큰 값"에서 "(arr[j] – j) 값 중 가장 작은 값"을 뺀 것과 같습니다. 따라서 배열을 한 번만 순회하면 답을 구할 수 있습니다.
- 전체 배열에서 (arr[i] – i)의 최댓값을 찾습니다.
- 전체 배열에서 (arr[i] – i)의 최솟값을 찾습니다.
- 위 두 값의 차이를 반환합니다.
i와 j는 서로 달라야 하지만, 하나의 순회 과정에서 최댓값과 최솟값이 같은 인덱스에서 갱신되더라도 결과적으로 서로 다른 두 위치의 조합이 항상 존재하므로(n ≥ 2인 경우) 문제없이 동작합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int getMaxDiff(int *arr, int n){
if (n < 2) {
cout << "Invalid input" << endl;
exit(1);
}
int minVal = INT_MAX;
int maxVal = INT_MIN;
for (int i = 0; i < n; ++i) {
int result = arr[i] - i;
if (result > maxVal) {
cout << "Max = " << arr[i] << " - " << i << endl;
maxVal = result;
}
if (result < minVal) {
cout << "Min = " << arr[i] << " - " << i << endl;
minVal = result;
}
}
return (maxVal - minVal);
}
int main(){
int arr[] = {7, 5, 10, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum value = " << getMaxDiff(arr, n) << endl;
return 0;
}
실행 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.
Max = 7 - 0
Min = 7 - 0
Min = 5 - 1
Max = 10 - 2
Min = 2 - 3
Maximum value = 9
출력 과정을 살펴보면, 인덱스 2의 요소 10에서 (10 – 2) = 8로 최댓값이 갱신되고, 인덱스 3의 요소 2에서 (2 – 3) = -1로 최솟값이 갱신됩니다. 최종적으로 8 – (-1) = 9가 반환됩니다.
복잡도 분석
- 시간 복잡도: O(n) — 배열을 한 번만 순회하면 됩니다.
- 공간 복잡도: O(1) — 추가 메모리 없이 상수 개의 변수만 사용합니다.