파이썬(Python)으로 배열 정렬에 필요한 최소 스왑 횟수 구하기

nums라는 이름의 배열이 주어졌을 때, 이 배열을 오름차순 또는 내림차순 중 어느 한쪽이라도 정렬된 상태로 만들기 위해 필요한 스왑(교환) 횟수의 최솟값을 구해야 합니다.

예를 들어 입력이 nums = [2, 5, 6, 3, 4]라고 가정해 보겠습니다. 이 경우 출력은 2가 됩니다. 처음 배열은 [2, 5, 6, 3, 4]입니다. 먼저 6과 4를 교환하면 [2, 5, 4, 3, 6]이 되고, 이어서 5와 3을 교환하면 [2, 3, 4, 5, 6]이 됩니다. 따라서 배열을 오름차순으로 정렬하는 데 총 2번의 스왑이 필요합니다.

문제 해결 접근 방법

이 문제는 사이클 분해(cycle detection) 개념을 활용해 다음 단계로 해결할 수 있습니다.

• swap_count() 함수를 정의합니다. 이 함수는 input_arr를 입력으로 받습니다.
  • pos := input_arr의 각 원소에 대해 (원래 위치, 값) 형태의 튜플을 담은 새로운 리스트
  • pos 리스트를 각 원소의 '값'을 기준으로 정렬
  • cnt := 0 으로 초기화
  • index를 0부터 input_arr의 크기만큼 반복:
    • 반복 조건이 참(True)인 동안:
      • pos[index][0]이 index와 같다면 → 루프 종료
      • 그렇지 않다면:
        • cnt를 1 증가
        • swap_index := pos[index][0]
        • pos[index]와 pos[swap_index]의 값을 서로 교환
  • cnt를 반환
• 메인 함수(solve)에서는 다음을 수행합니다:
  • swap_count(input_arr)와 swap_count(역순으로 뒤집은 배열) 중 더 작은 값을 반환

여기서 역순 배열의 스왑 횟수까지 함께 계산하는 이유는, 내림차순 정렬이 더 적은 교환으로 끝나는 경우도 있기 때문입니다. 두 방향 중 최솟값을 선택하면 어떤 순서로 정렬하든 필요한 최소 스왑 횟수를 얻을 수 있습니다.

예제 코드

아래 파이썬 구현 예제를 통해 더 자세히 이해해 보겠습니다.

def swap_count(input_arr):
   pos = sorted(list(enumerate(input_arr)), key=lambda x: x[1])
   cnt = 0

   for index in range(len(input_arr)):
       while True:
           if (pos[index][0] == index):
               break
           else:
               cnt += 1
               swap_index = pos[index][0]
               pos[index], pos[swap_index] = pos[swap_index], pos[index]

   return cnt

def solve(input_arr):
   return min(swap_count(input_arr), swap_count(input_arr[::-1]))

nums = [2, 5, 6, 3, 4]
print(solve(nums))

입력

[2, 5, 6, 3, 4]

출력

2

정렬 기준이 되는 sorted 연산 때문에 전체 시간 복잡도는 O(n log n)이며, 실제 스왑 계산 과정은 각 원소를 한 번씩 방문하는 수준인 O(n)으로 처리됩니다. 덕분에 비교적 큰 배열에서도 효율적으로 최소 스왑 횟수를 구할 수 있습니다.