C++로 두 번째 배열의 모든 요소를 순서대로 포함하는 최소 길이 부분 배열 찾기

크기가 각각 n과 m인 두 개의 배열 A와 B가 있다고 가정해 봅시다. 이때 우리의 목표는 배열 A에서 배열 B의 모든 요소를 포함하면서 길이가 가장 짧은 부분 배열(subarray)을 찾는 것입니다. 단, B의 요소들은 A 안에서 연속적으로 존재하지 않아도 되지만, 반드시 동일한 순서를 유지해야 합니다.

예를 들어 A = [2, 2, 4, 5, 8, 9], B = [2, 5, 9]라고 할 때, 정답은 5입니다. A에서 가장 짧은 부분 배열은 [2, 4, 5, 8, 9]이며, 여기에는 B의 요소인 2, 5, 9가 모두 같은 순서로 포함되어 있기 때문입니다.

접근 방법

이 문제는 다음과 같은 방식으로 해결할 수 있습니다.

• 배열 A를 처음부터 순회하면서 B의 첫 번째 요소와 일치하는 위치를 찾습니다.
• 첫 번째 요소가 일치하면, 그 지점부터 A를 계속 탐색하며 B의 나머지 요소들이 순서대로 등장하는지 확인합니다.
• B의 모든 요소가 매칭되면 해당 구간의 길이를 계산하고, 기존에 저장된 최소 길이보다 작다면 값을 갱신합니다.
• 모든 탐색이 끝나면 최종적으로 구해진 최소 길이를 반환합니다.

C++ 구현 예제

#include<iostream>
using namespace std;
int lengthMinSubarray(int A[], int n, int B[], int m) {
    int res = INT_MAX;
    for (int i = 0; i < n - m + 1; i++) {
        if (A[i] == B[0]) {
            int j = 0, idx = i;
            for (; idx < n; idx++) {
                if (A[idx] == B[j])
                    j++;
                if (j == m)
                    break;
            }
            if (j == m && res > idx - i + 1)
                res = (idx == n) ? idx - i : idx - i + 1;
        }
    }
    return res;
}
int main() {
    int A[] = { 5, 6, 5, 2, 7, 5, 6, 7, 5, 5, 7 };
    int B[] = { 5, 5, 7 };
    int n = sizeof(A)/sizeof(A[0]);
    int m = sizeof(B)/sizeof(B[0]);
    cout << "Minimum length of subarray: " << lengthMinSubarray(A, n, B, m);
}

실행 결과

Minimum length of subarray: 3

위 예제에서 배열 A = [5, 6, 5, 2, 7, 5, 6, 7, 5, 5, 7], B = [5, 5, 7]일 때, B의 모든 요소를 순서대로 포함하는 가장 짧은 부분 배열은 [5, 5, 7]이므로 결과값으로 3이 출력됩니다.