C++로 서로 다른 두 숫자의 인덱스 간 최대 차이 찾기

이번 문제에서는 n개의 정수로 구성된 배열 arr[]가 주어지며, C++로 서로 다른 두 숫자의 인덱스 간 최대 차이를 찾는 프로그램을 작성하는 것이 목표입니다.

문제 설명

배열에 있는 정수값들의 인덱스 차이 중에서 최댓값을 구해야 하며, 단, 비교 대상이 되는 두 정수는 서로 다른 값이어야 한다는 조건이 있습니다. 값이 같은 요소끼리의 인덱스 차이는 계산에서 제외됩니다.

예시로 이해하기

입력

arr[] = {4, 1, 3, 2, 1, 2, 4}

출력

5

설명

인덱스 0의 요소 4와 인덱스 5의 요소 2는 서로 다른 값이며, 두 인덱스의 차이는 5 − 0 = 5로 가능한 최댓값입니다.

해결 접근 방식

이 문제의 핵심은 배열의 첫 번째 요소에 주목하는 것입니다. 최대 인덱스 차이를 만드는 쌍에는 항상 첫 번째 요소가 포함되거나, 그렇지 않은 경우에는 첫 번째 요소와 마지막 요소의 값이 서로 달라 전체 범위(n−1)가 곧 정답이 됩니다. 따라서 다음 두 지점만 확인하면 됩니다.

• 배열 앞쪽부터 스캔하여 첫 번째 요소와 값이 다른 가장 가까운 인덱스를 찾습니다.
• 배열 뒤쪽부터 스캔하여 첫 번째 요소와 값이 다른 가장 먼 인덱스를 찾습니다.

두 결과 중 더 큰 값이 곧 정답이며, 배열의 모든 요소 값이 동일한 경우에는 0을 반환합니다.

솔루션 구현 코드는 다음과 같습니다.

예제 코드

#include <iostream>
using namespace std;

int maximum(int a, int b){
    if(a > b)
        return a;
    return b;
}

int CalcMaxIndDiff(int a[], int n) {
    int indDiff1 = 0, indDiff2 = 0;
    int i = 0;
    // 앞쪽부터 스캔: 첫 번째 요소와 값이 다른 가장 가까운 인덱스
    while(i < (n - 1)){
        if(a[0] != a[i]){
            indDiff2 = i;
            break;
        }
        i++;
    }
    // 뒤쪽부터 스캔: 첫 번째 요소와 값이 다른 가장 먼 인덱스
    i = (n - 1);
    while(i > 0){
        if(a[0] != a[i]){
            indDiff1 = i;
            break;
        }
        i--;
    }
    return maximum(indDiff1, indDiff2);
}

int main() {
    int arr[] = { 4, 1, 3, 2, 1, 2, 4 };
    int n = 7;
    cout<<"서로 다른 두 숫자의 인덱스 간 최대 차이는 "<<CalcMaxIndDiff(arr, n);
    return 0;
}

실행 결과

서로 다른 두 숫자의 인덱스 간 최대 차이는 5

복잡도 분석

시간 복잡도는 배열을 앞뒤로 최대 두 번 선형 탐색하므로 O(n)이며, 추가적인 자료 구조를 사용하지 않으므로 공간 복잡도는 O(1)입니다.