C++로 정렬되지 않은 배열에서 두 숫자 간의 최소 거리 구하기

정렬되지 않은 배열 A와 두 개의 숫자 x, y가 주어졌을 때, 배열 A 안에서 x와 y 사이의 최소 거리를 찾는 문제를 살펴보겠습니다. 배열에는 중복된 요소가 포함될 수도 있습니다.

예를 들어, 배열이 A = [2, 5, 3, 5, 4, 4, 2, 3]이고 x = 3, y = 2라고 가정해 봅시다. 이 경우 3과 2 사이의 최소 거리는 1입니다.

문제 해결 접근 방식

이 문제는 다음 단계를 따라 해결할 수 있습니다.

배열을 왼쪽에서 오른쪽으로 순회하다가 x 또는 y를 처음 발견하면 탐색을 멈추고, 해당 위치의 인덱스를 prev 변수에 저장합니다.
이후 prev 인덱스 다음부터 계속 배열을 순회합니다. 현재 인덱스 i의 요소가 x 또는 y와 일치하는 경우, 그 값이 A[prev]와 다른지 확인합니다. 값이 서로 다르다면 필요에 따라 최소 거리를 갱신하고, 마지막으로 prev := i로 업데이트합니다.

C++ 구현 예제

#include<iostream>
using namespace std;
int findMinDistance(int A[], int n, int x, int y) {
    int i = 0;
    int distance = INT_MAX;
    int prev_index;
    for (i = 0; i < n; i++) {
        if (A[i] == x || A[i] == y) {
            prev_index = i;
            break;
        }
    }
    while (i < n) {
        if (A[i] == x || A[i] == y) {
            if ( A[prev_index] != A[i] && (i - prev_index) < distance ){
                distance = i - prev_index;
                prev_index = i;
            } else
                prev_index = i;
        }
        i++;
    }
    return distance;
}
int main() {
    int arr[] = {2, 5, 3, 5, 4, 4, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 3;
    int y = 2;
    cout << "Minimum distance between " << x << " and " << y << " is: "<< findMinDistance(arr, n, x, y);
}

실행 결과

Minimum distance between 3 and 2 is: 1

알고리즘 설명

위 코드의 동작 원리를 좀 더 자세히 살펴보겠습니다.

초기 탐색: 먼저 for 루프를 사용하여 배열의 처음부터 x 또는 y가 나타나는 첫 번째 위치를 찾아 그 인덱스를 prev_index에 저장한 후 반복문을 종료합니다.
거리 계산: 이후 while 루프에서 남은 배열을 순회하며 x 또는 y와 일치하는 요소를 만날 때마다 이전 저장 위치(prev_index)와 비교합니다. 두 요소의 값이 서로 다르면서(즉, 하나는 x, 하나는 y인 경우) 현재 거리가 기존 최소 거리보다 작으면 거리를 갱신합니다.
최적화 포인트: 같은 값(x 또는 y)이 연속해서 나타나는 경우에는 거리를 계산하지 않고 prev_index만 업데이트하므로, 불필요한 비교 연산을 줄일 수 있습니다.

이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 공간은 상수 수준(O(1))만 사용하기 때문에 매우 효율적입니다.