C++로 두 배열 간의 호환성 차이(순위 불일치 횟수) 구하기

두 친구가 서로의 궁합을 시험해 보려고 합니다. 1부터 n까지 번호가 붙은 영화 목록이 주어지면, 두 사람은 각자 영화에 순위를 매기게 됩니다. 이때 두 사람 사이의 호환성 차이(compatibility difference)란, 같은 영화에 대해 서로 매긴 상대적 순위가 얼마나 어긋나는지를 나타내는 불일치 횟수입니다.

예를 들어 A = [3, 1, 2, 4, 5], B = [3, 2, 4, 1, 5]라면 결과는 2가 됩니다. 첫 번째 사람은 영화 1을 영화 2와 4보다 앞선 순위로 평가했지만, 두 번째 사람은 그 반대로 평가했기 때문입니다.

접근 방법

이 문제는 배열 B를 배열 A와 완전히 같아질 때까지 변형하는 데 필요한 최소 인접 스왑(adjacent swap) 횟수를 세는 것과 본질적으로 같습니다. 알고리즘의 흐름은 다음과 같습니다.

• 두 배열을 처음부터 끝까지 순회합니다.
• 현재 위치 i에서 A[i]와 B[i]가 같다면 아무 작업도 하지 않습니다.
• 값이 다르다면, B 배열에서 A[i]와 일치하는 요소의 위치 j를 찾습니다.
• B[j]를 한 칸씩 앞으로 스왑하여 B[i] 위치로 이동시키고, 스왑할 때마다 카운트(result)를 1씩 증가시킵니다.

최악의 경우 시간 복잡도는 O(n²)이며, 추가 메모리 없이 제자리(in-place)에서 해결할 수 있다는 장점이 있습니다.

예제 코드

#include<iostream>
using namespace std;

int getArrayDiff(int A[], int B[], int n) {
    int result = 0;

    for (int i = 0; i < n; i++) {
        if (A[i] != B[i]) {

            // B 배열에서 A[i]와 같은 값의 위치를 찾음
            int j = i + 1;
            while (A[i] != B[j])
                j++;

            // 해당 요소를 앞쪽으로 한 칸씩 이동
            while (j != i) {
                swap(B[j], B[j - 1]);
                j--;
                result++;
            }
        }
    }
    return result;
}

int main() {
    int A[] = { 3, 1, 2, 4, 5 };
    int B[] = { 3, 2, 4, 1, 5 };
    int n = sizeof(A)/sizeof(A[0]);

    cout << "Compatibility difference: " << getArrayDiff(A, B, n);
}

실행 결과

Compatibility difference: 2