[0, n – 1] 범위의 고유한 값을 가진 num이라는 배열이 있다고 가정합니다. 이 배열은 정렬되지 않았습니다. 또한 각 쌍에 배열의 요소를 교환할 수 있는 인덱스가 포함된 또 다른 쌍의 배열이 있습니다. 여러 번 교환할 수 있습니다. 이러한 스왑을 사용하여 배열을 정렬된 순서로 정렬할 수 있는지 여부를 확인해야 합니다.
따라서 입력이 nums =[6,1,7,3,0,5,4,2] pair =[(0,4),(6,0),(2,7)]과 같으면 인덱스(2,7)를 스왑할 수 있으므로 출력은 True입니다. 배열은 [6,1,2,3,0,5,4,7]이 되고 스왑(6,0)은 배열이 [4, 1,2,3,0,5,6,7]을 선택한 다음 (0,4)를 교체하여 [0,1,2,3,4,5,6,7]을 얻습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- N :=숫자의 크기, P :=쌍 배열의 쌍 수
- v :=N개의 하위 목록이 있는 목록
- 방문함:=새로운 세트
- 0에서 P 사이의 i에 대해 다음을 수행합니다.
- 쌍의 두 번째 인덱스[i]를 v[쌍의 첫 번째 인덱스[i]]에 삽입
- 쌍의 첫 번째 인덱스[i]를 v[쌍의 두 번째 인덱스[i]]에 삽입
- 0~N 범위의 i에 대해 다음을 수행합니다.
- 내가 방문하지 않으면
- que :=이중 종료 대기열
- arr_first :=새 목록
- arr_second :=새 목록
- 방문한 것으로 표시
- que 끝에 i 삽입
- que가 비어 있지 않은 동안 do
- u :=que의 앞 요소 및 que의 앞 요소 삭제
- arr_first의 끝에 u를 삽입
- arr_second 끝에 nums[u] 삽입
- v[u]의 각 s에 대해
- s를 방문하지 않으면
- 방문한 것으로 표시
- queue 끝에 s 삽입
- s를 방문하지 않으면
- arr_first :=목록 정렬 arr_first
- arr_second :=목록 정렬 arr_second
- arr_first가 arr_second와 같지 않으면
- 거짓을 반환
- 내가 방문하지 않으면
- 참 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시 코드
from collections import deque def solve(nums, pairs): N = len(nums) P = len(pairs) v = [[] for i in range(N)] visited = set() for i in range(P): v[pairs[i][0]].append(pairs[i][1]) v[pairs[i][1]].append(pairs[i][0]) for i in range(N): if i not in visited: que = deque() arr_first = [] arr_second = [] visited.add(i) que.append(i) while len(que) > 0: u = que.popleft() arr_first.append(u) arr_second.append(nums[u]) for s in v[u]: if s not in visited: visited.add(s) que.append(s) arr_first = sorted(arr_first) arr_second = sorted(arr_second) if arr_first != arr_second: return False return True nums = [6,1,7,3,0,5,4,2] pairs = [(0,4),(6,0),(2,7)] print(solve(nums, pairs))
입력
[6,1,7,3,0,5,4,2], [(0,4),(6,0),(2,7)]
출력
True