정수로 이루어진 배열이 하나 주어집니다. 우리가 해야 할 일은 값과 인덱스 차이 합의 최대 절댓값을 구하는 것입니다. 즉, 배열 내 모든 인덱스 쌍 (i, j)에 대해 |Arr[i] − Arr[j]| + |i − j|를 계산한 뒤, 그중 가장 큰 값을 찾으면 됩니다. 여기서 |A|는 A의 절댓값을 의미합니다.
예를 들어 배열의 요소가 4개라면 인덱스는 0, 1, 2, 3이 되고, 가능한 고유한 쌍은 (0,0), (1,1), (2,2), (3,3), (0,1), (0,2), (0,3), (1,2), (1,3), (2,3) 입니다.
입력 및 출력 예시
입력 − Arr[] = { 1, 2, 4, 5 }
출력 − 값과 인덱스 차이 합의 최대 절댓값 − 7
설명 − 각 인덱스 쌍별로 |A[i] − A[j]| + |i − j|를 계산하면 다음과 같습니다.
1. (0,0), (1,1), (2,2), (3,3) --------- 각각 |i-j| = 0 2. (0,1) ---------- |1-2| + |0-1| = 1+1 = 2 3. (0,2) ---------- |1-4| + |0-2| = 3+2 = 5 4. (0,3) ---------- |1-5| + |0-3| = 4+3 = 7 5. (1,2) ---------- |2-4| + |1-2| = 2+1 = 3 6. (1,3) ---------- |2-5| + |1-3| = 3+2 = 5 7. (2,3) ---------- |4-5| + |2-3| = 1+1 = 2 따라서 최댓값은 7입니다.
입력 − Arr[] = { 10, 20, 21 }
출력 − 값과 인덱스 차이 합의 최대 절댓값 − 13
설명 − 각 인덱스 쌍별 계산 결과는 다음과 같습니다.
1. (0,0), (1,1), (2,2) --------- 각각 |i-j| = 0 2. (0,1) ---------- |10-20| + |0-1| = 10+1 = 11 3. (0,2) ---------- |10-21| + |0-2| = 11+2 = 13 4. (1,2) ---------- |20-21| + |1-2| = 1+1 = 2 따라서 최댓값은 13입니다.
문제 해결 접근 방식
정수 배열 Arr[]를 입력으로 받습니다.
maxabsDiff(int arr[], int n) 함수가 값과 인덱스 차이 합의 최대 절댓값을 계산합니다.
결과를 저장할 변수 result를 0으로 초기화합니다.
바깥쪽 for 루프에서 배열을 처음부터 끝까지 순회합니다.
안쪽 for 루프에서 나머지 요소들을 순회하며 abs(arr[i] − arr[j]) + abs(i − j)를 계산하여 변수 absDiff에 저장합니다.
새로 계산된 값이 기존 result보다 크면 result를 해당 값으로 갱신합니다.
배열 전체를 순회한 후 result를 반환합니다.
구현 예제 코드
#include <stdio.h>
#include <math.h>
// 최대 절댓값 차이를 반환하는 함수
int maxabsDiff(int arr[], int n){
int result = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int absDiff = abs(arr[i] - arr[j]) + abs(i - j);
if (absDiff > result)
result = absDiff;
}
}
return result;
}
int main(){
int Arr[] = {1,2,4,1,3,4,2,5,6,5};
printf("Maximum absolute difference of value and index sums: %d", maxabsDiff(Arr,10));
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
Maximum absolute difference of value and index sums: 13