길이가 같은 두 개의 정수 배열 src와 tgt가 있다고 가정합니다. 또한 allowedSwaps[i]에 (ai, bi) 쌍이 포함된 allowedSwaps 배열이 있습니다. 이는 인덱스 ai에 있는 요소를 배열 src의 요소 인덱스 bi와 교환할 수 있음을 나타냅니다. (어떤 순서로든 원하는 만큼 특정 인덱스 쌍에서 요소를 교환할 수 있습니다.) 길이가 같은 두 배열 src와 tgt의 해밍 거리는 요소가 다른 위치의 수라는 것을 알 수 있습니다. 배열 src에서 스왑 작업을 수행한 후 src와 tgt의 최소 해밍 거리를 찾아야 합니다.
따라서 입력이 src =[2,3,4,5], tgt =[3,2,5,6], allowedSwaps =[[0,1],[2,3]]인 경우 출력은 src는 다음과 같은 방식으로 변환될 수 있기 때문에 1이 됩니다. 인덱스 0과 1을 바꾸므로 소스 =[3,2,4,5], 인덱스 2와 3을 바꾸므로 소스 =[3,2,5,4] . 여기에서 src와 tgt의 해밍 거리는 인덱스 3이라는 1개의 위치에서 다르기 때문에 1입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- graph :=src와 크기가 같고 n으로 채워진 목록
- find() 함수를 정의합니다. 시간이 걸립니다.
- 그래프[x]가 x와 같지 않은 동안 do
- 그래프[x] :=그래프[그래프[x]]
- x :=그래프[x]
- 반환 x
- union() 함수를 정의합니다. x, y 가 걸립니다.
- x1 :=찾기(x), y1 :=찾기(y)
- 그래프[x1] :=y1
- 메인 방법에서 다음을 수행합니다.
- allowedSwap의 각 쌍(x, y)에 대해 다음을 수행합니다.
- 결합(x, y)
- 그룹:=값이 목록인 맵, 기본적으로 목록이 비어 있음
- 0 ~ src - 1 크기 범위의 i에 대해
- i1 :=찾기(i)
- 그룹 끝에 i 삽입[i1]
- ans :=0
- 그룹의 모든 값 목록에 있는 각 id에 대해 다음을 수행합니다.
- counter :=count 값을 담기 위한 빈 지도
- id의 각 idx에 대해 다음을 수행합니다.
- 카운터[src[idx]] :=카운터[src[idx]] + 1
- 카운터[tgt[idx]] :=카운터[tgt[idx]] - 1
- ans :=ans + (counter 값 목록의 모든 var에 대한 val의 모든 절대값 합계)/2
- 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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]]
출력
1