정렬되어 있지 않은 정수 배열이 주어졌을 때, 이 배열을 정렬한 상태에서 인접한 두 요소 사이의 최대 차이를 구하는 것이 이 글의 목표입니다. 해결 과정은 간단합니다. 먼저 배열을 오름차순으로 정렬한 뒤, 배열을 순회하면서 인접 요소 간 차이 Arr[i+1]−Arr[i]를 계산하고, 매 단계마다 지금까지 발견한 최댓값과 비교하여 더 큰 값이 나오면 갱신해 주면 됩니다.
예제 1
입력 − Arr[] = [ 1, 5, 10, 2, 7 ]
출력 − 정렬된 형태의 배열에서 최대 인접 차이는 3입니다.
설명 − 배열을 오름차순으로 정렬하면 [ 1, 2, 5, 7, 10 ]이 되며, 인접 요소 간 차이는 다음과 같습니다.
Arr[1]−Arr[0] = 1, 최대 차이 = 1 Arr[2]−Arr[1] = 3, 최대 차이 = 3 Arr[3]−Arr[2] = 2, 최대 차이 = 3 Arr[4]−Arr[3] = 3, 최대 차이 = 3
예제 2
입력 − Arr[] = [ 5, 11, 21, 15, 20 ]
출력 − 정렬된 형태의 배열에서 최대 인접 차이는 6입니다.
설명 − 배열을 오름차순으로 정렬하면 [ 5, 11, 15, 20, 21 ]이 되며, 인접 요소 간 차이는 다음과 같습니다.
Arr[1]−Arr[0] = 6, 최대 차이 = 6 Arr[2]−Arr[1] = 4, 최대 차이 = 6 Arr[3]−Arr[2] = 5, 최대 차이 = 6 Arr[4]−Arr[3] = 1, 최대 차이 = 6
알고리즘 접근 방식
- 정수 배열 Arr[]를 입력받습니다.
- 배열을 오름차순으로 정렬합니다.
- 지금까지 발견한 인접 요소 간 최대 차이를 저장할 변수 MaxD를 선언하고, 초기값을 Arr[1]−Arr[0]으로 설정합니다.
- 두 번째 요소부터 마지막에서 두 번째 요소 인덱스까지 반복문을 실행합니다.
- 계산한 차이 Arr[i+1]−Arr[i]가 MaxD보다 크면 MaxD를 해당 값으로 갱신합니다.
- 마지막에서 두 번째 요소 인덱스에 도달할 때까지 위 과정을 반복합니다.
- 결과값 MaxD를 최대 인접 요소 차이로 출력합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int max_adj_Diff(int A[], int size){
int MaxD = A[1] - A[0];
for(int i = 1; i < size - 1; i++){
if(A[i+1] - A[i] > MaxD)
MaxD = A[i+1] - A[i];
}
return MaxD;
}
int main(){
int Arr[] = {1, 5, 2, 18, 20, 13};
sort(Arr, Arr + 6); // 배열을 오름차순으로 정렬
int md = max_adj_Diff(Arr, 6);
cout << "정렬된 배열에서 최대 인접 차이 : " << md;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
정렬된 배열에서 최대 인접 차이 : 8
배열 {1, 5, 2, 18, 20, 13}을 오름차순으로 정렬하면 {1, 2, 5, 13, 18, 20}이 됩니다. 이때 인접 요소 간 차이는 각각 1, 3, 8, 5, 2이므로 최댓값인 8이 결과로 출력됩니다.
시간 복잡도
배열 정렬에 O(n log n), 정렬된 배열을 한 번 순회하는 데 O(n)이 소요되므로, 전체 시간 복잡도는 O(n log n)입니다. 추가로 사용되는 메모리는 상수 수준이므로 공간 복잡도는 O(1)입니다.