크기가 N인 정수 배열이 주어지며, 배열의 요소들은 무작위 순서로 배치되어 있습니다. 이 문제의 목표는 더 큰 요소가 더 작은 숫자 뒤에 나타나는 두 요소를 찾아 그 차이를 최대화하는 것입니다. 즉, Arr[j] − Arr[i]가 최대가 되도록 j > i를 만족하는 조합을 구해야 합니다.
입력 및 출력 예시
입력 1
Arr[] = { 2, 1, 3, 8, 3, 19, 21 }출력 — 더 큰 요소가 더 작은 숫자 뒤에 나타나는 두 요소 사이의 최대 차이: 20
설명 — 최대 차이는 21과 1 사이에서 발생하며, 배열에서 21은 1 뒤에 위치합니다.
입력 2
Arr[] = { 18, 2, 8, 1, 2, 3, 2, 6 }출력 — 더 큰 요소가 더 작은 숫자 뒤에 나타나는 두 요소 사이의 최대 차이: 6
설명 — 최대 차이는 8과 2 사이에서 발생하며, 배열에서 8은 2 뒤에 위치합니다.
문제 해결 접근 방식
- 정수 배열(Arr[])과 배열의 크기(n)를 선언합니다.
- maxDiff(int arr[], int n) 함수는 위 조건을 만족하는 두 요소의 최대 차이를 계산하며, 입력 배열과 그 크기를 인자로 받습니다.
- 함수 내부에는 지금까지 발견한 최대 차이를 저장할 변수 MD를 선언하고, 초기값으로 arr[1] − arr[0]을 설정합니다.
- 또한 지금까지 순회한 요소 중 최솟값을 저장할 변수 min을 선언하고, 초기값으로 arr[0]을 설정합니다.
- 배열을 한 번 순회하면서 다음 두 가지를 확인합니다.
- 현재 요소(arr[i])에서 min을 뺀 값이 MD보다 크면 MD를 갱신합니다.
- 현재 요소가 min보다 작으면 min을 현재 요소로 갱신합니다. - 순회가 끝나면 MD를 반환합니다.
- 이 방식은 배열을 한 번만 훑으면 되므로 시간 복잡도는 O(n)으로 매우 효율적입니다.
예제 코드
#include <stdio.h>
int maxDiff(int arr[], int n){
// 지금까지 발견된 최대 차이
int MD = arr[1] - arr[0];
// 지금까지 방문한 요소 중 최솟값
int min = arr[0];
for(int i = 1; i < n; i++){
if (arr[i] - min > MD)
MD = arr[i] - min;
if (arr[i] < min)
min = arr[i];
}
return MD;
}
/* 위 함수를 테스트하기 위한 드라이버 프로그램 */
int main(){
int arr[] = {2,5,7,3,4,12};
int n=6;
// 함수 호출
printf("Maximum difference is : %d ",maxDiff(arr, n));
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Maximum difference is : 10
예제 배열 {2, 5, 7, 3, 4, 12}에서 최대 차이는 12와 2 사이의 값인 10이며, 12는 2 뒤에 위치하므로 조건을 만족합니다.