C++ 배열에서 두 요소 간 최대 차이(가장 큰 간격) 구하기

이 튜토리얼에서는 주어진 배열에서 두 요소 사이의 가장 큰 차이(최대 간격)를 구하는 C++ 프로그램을 작성해 보겠습니다.

배열에서 가장 큰 값과 가장 작은 값을 찾은 뒤, 그 차이를 계산하면 됩니다. 이 방법은 배열을 한 번만 순회하면 되기 때문에 시간 복잡도가 O(n)으로 매우 효율적입니다.

문제 해결 단계

• 배열을 초기화합니다.
• 배열을 순회하면서 최댓값(max)과 최솟값(min)을 찾습니다.
• max - min 값을 반환합니다.

예제 코드

다음은 위 알고리즘을 구현한 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int findLargestGap(int arr[], int n) {
    int max = arr[0], min = arr[0];
    for (int i = 0; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
        if (arr[i] < min) {
            min = arr[i];
        }
    }
    return max - min;
}

int main() {
    int arr[] = {3, 4, 1, 6, 5, 6, 9, 10};
    cout << findLargestGap(arr, 8) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

9

동작 원리 설명

예제 배열 {3, 4, 1, 6, 5, 6, 9, 10}에서 최댓값은 10, 최솟값은 1입니다. 따라서 가장 큰 간격은 10 - 1 = 9가 됩니다.

이 코드는 배열의 첫 번째 요소로 max와 min을 초기화한 후, 배열 전체를 한 번씩만 확인하면서 더 큰 값이나 더 작은 값이 나타날 때마다 갱신합니다. 모든 요소를 확인한 후에는 두 값의 차이를 반환하므로, 정렬 없이도 선형 시간(O(n))에 문제를 해결할 수 있습니다.

마무리

이번 튜토리얼에서는 배열 내 두 요소 간의 최대 차이를 구하는 간단하고 효율적인 방법을 살펴보았습니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.