Python으로 스왑 연산 후 해밍 거리 최소화하기: 유니온-파인드 활용법

문제 소개

길이가 같은 두 개의 정수 배열 src와 tgt가 있다고 가정해 봅시다. 추가로 allowedSwaps 배열이 주어지는데, allowedSwaps[i]는 쌍 (ai, bi)를 담고 있으며, 이는 src 배열의 ai번 인덱스 원소와 bi번 인덱스 원소를 서로 교환할 수 있음을 의미합니다. 특정 인덱스 쌍은 원하는 만큼 몇 번이든, 어떤 순서로든 교환이 가능합니다.

여기서 해밍 거리(Hamming Distance)란 길이가 같은 두 배열에서 원소가 서로 다른 위치의 개수를 뜻합니다. 우리가 구해야 하는 것은 src 배열에 임의의 횟수만큼 교환(swap) 연산을 수행한 뒤의 src와 tgt 사이 최소 해밍 거리입니다.

예를 들어 입력이 src = [2,3,4,5], tgt = [3,2,5,6], allowedSwaps = [[0,1],[2,3]]이라면 출력은 1입니다. 인덱스 0과 1을 교환하면 src = [3,2,4,5]가 되고, 이어서 인덱스 2와 3을 교환하면 src = [3,2,5,4]가 됩니다. 이 상태에서 두 배열은 인덱스 3 한 곳에서만 다르므로 해밍 거리는 1이 됩니다.

접근 방법: 유니온-파인드(Union-Find)

교환 관계로 연결된 인덱스들은 서로에게 영향을 주고받을 수 있으므로, 이들을 하나의 그룹으로 묶으면 해당 그룹 안에서는 원소를 자유롭게 재배치할 수 있습니다. 따라서 유니온-파인드(서로소 집합) 자료구조로 교환 가능한 인덱스들을 집합으로 묶은 뒤, 각 집합 안에서 src와 tgt의 원소 빈도 차이를 계산하면 됩니다.

알고리즘 단계

초기화: src와 같은 크기의 리스트 graph를 만들고 각 원소를 자기 인덱스 값으로 채웁니다.
find(x) 함수 정의: graph[x]가 x와 같아질 때까지 graph[x] := graph[graph[x]], x := graph[x]를 반복한 뒤 x를 반환합니다. (경로 압축으로 탐색 속도 향상)
union(x, y) 함수 정의: x1 := find(x), y1 := find(y)를 구한 뒤 graph[x1] := y1로 두 집합을 하나로 합칩니다.
그룹 형성: allowedSwaps의 모든 쌍 (x, y)에 대해 union(x, y)를 호출합니다. 이후 groups := 값이 리스트인 맵(기본값은 빈 리스트)을 만들고, i를 0부터 len(src)-1까지 순회하며 i1 := find(i)를 키로 groups[i1] 끝에 i를 삽입합니다.
그룹별 비교: ans := 0으로 초기화한 뒤, groups의 각 값(ids)마다 counter := 빈 카운터 맵을 만들고, ids의 각 idx에 대해 counter[src[idx]] += 1, counter[tgt[idx]] -= 1을 수행합니다.
결과 누적: ans := ans + (counter 값들의 절대값 합)/2를 계산하고, 모든 그룹을 처리한 후 ans를 반환합니다.

절대값의 합을 2로 나누는 이유는, 그룹 안에서 서로 매칭되지 못한 원소 하나당 +1과 −1이 각각 한 번씩 기록되어 불일치 개수가 두 배로 집계되기 때문입니다.

예제 구현

아래 파이썬 구현을 통해 더 자세히 이해해 봅시다.

from collections import defaultdict, Counter
def solve(src, tgt, allowedSwaps):
    graph = [ n for n in range(len(src)) ]

    def find(x):
        while graph[x] != x:
            graph[x] = graph[graph[x]]
            x = graph[x]
        return x

    def union(x, y):
        x1, y1 = find(x), find(y)
        graph[x1] = y1

    for x, y in allowedSwaps:
        union(x,y)

    groups = defaultdict(list)
    for i in range(len(src)):
        i1 = find(i)
        groups[i1].append(i)

    ans = 0
    for ids in groups.values():
        counter = Counter()
        for idx in ids:
            counter[src[idx]] += 1
            counter[tgt[idx]] -= 1
        ans += sum( abs(val) for val in counter.values())/2
    return ans

src = [2,3,4,5]
tgt = [3,2,5,6]
allowedSwaps = [[0,1],[2,3]]
print(solve(src, tgt, allowedSwaps))

실행 결과

입력

[2,3,4,5], [3,2,5,6], [[0,1],[2,3]]

출력

복잡도 분석

경로 압축이 적용된 유니온-파인드 연산은 거의 상수 시간(α(N))에 처리되므로, 전체 시간 복잡도는 O(N + M)입니다. 여기서 N은 배열의 길이, M은 allowedSwaps의 길이입니다. 그룹 정보를 저장하기 위한 공간 복잡도는 O(N)입니다.