Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

Python으로 주어진 인덱스 쌍의 교환만으로 배열 정렬 가능 여부 확인하기

문제 이해하기

0부터 n-1까지의 고유한 값으로 구성된 배열 nums가 있다고 가정해 봅시다. 이 배열은 현재 정렬되어 있지 않습니다. 또 다른 입력으로 인덱스 쌍(pair) 목록이 주어지는데, 각 쌍은 배열 내에서 원소를 서로 교환(swap)할 수 있는 두 인덱스를 의미합니다. 교환은 원하는 만큼 여러 번 반복할 수 있으며, 우리는 주어진 교환 규칙만을 사용해 배열을 오름차순으로 정렬할 수 있는지 판별해야 합니다.

예를 들어 입력이 다음과 같다고 해보겠습니다.

  • nums = [6,1,7,3,0,5,4,2]
  • pairs = [(0,4), (6,0), (2,7)]

이 경우 출력은 True입니다. 실제 정렬 과정은 다음과 같습니다.

  • (2,7) 교환 → [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] (정렬 완료)

접근 방법: 그래프와 연결 요소

핵심 아이디어는 그래프 이론에 있습니다. 서로 교환이 허용된 인덱스들을 하나의 연결 요소(connected component)로 묶으면, 같은 연결 요소에 속한 인덱스들은 어떤 순서로든 자유롭게 재배치할 수 있습니다. 따라서 다음 단계로 문제를 해결할 수 있습니다.

  • N := nums의 크기, P := pairs 배열의 쌍 개수
  • v := N개의 빈 하위 리스트를 가진 인접 리스트 생성
  • visited := 방문 여부를 추적하는 새로운 집합
  • 0부터 P-1까지 반복하며 각 쌍의 양방향 간선을 인접 리스트에 추가
  • 0부터 N-1까지 각 인덱스에 대해 아직 방문하지 않았다면 BFS 수행:
    • que := 덱(deque) 초기화
    • arr_first := 해당 연결 요소의 인덱스를 저장하는 리스트
    • arr_second := 해당 연결 요소의 값(nums[u])을 저장하는 리스트
    • i를 방문 처리하고 que에 삽입
    • que가 빌 때까지 앞 요소 u를 꺼내 arr_first에는 u를, arr_second에는 nums[u]를 추가하고, 인접한 미방문 노드 s를 큐에 삽입
    • 두 리스트를 각각 정렬한 뒤 비교하여, 서로 다르면 False 반환
  • 모든 연결 요소가 조건을 만족하면 True 반환

이 방법이 작동하는 이유는 간단합니다. 연결 요소 내부에서는 인덱스들이 임의로 재배치 가능하므로, 그 위치에 놓인 값들도 자유롭게 섞일 수 있습니다. 정렬된 최종 상태에서 특정 인덱스 집합이 가져야 할 값들은 "그 인덱스들이 현재 가진 값들을 정렬한 것"과 정확히 일치해야 합니다. 만약 정렬된 인덱스 목록과 정렬된 값 목록이 다르다면, 어떤 교환을 몇 번 반복하더라도 해당 구간을 올바르게 정렬할 수 없습니다.

구현 코드

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

복잡도 분석

시간 복잡도는 O(N + P + N log N)입니다. 모든 노드와 간선을 한 번씩 탐색하고(O(N + P)), 각 연결 요소마다 정렬을 수행하기 때문에 전체적으로 O(N log N)의 정렬 비용이 추가됩니다. 공간 복잡도는 인접 리스트와 방문 집합, 큐에 필요한 O(N + P)입니다.