Minimum Swaps 2

Sorted array를 만들기 위해서 몇 번의 swap이 필요한지를 찾는 문제이다.

Problem

You are given an unordered array consisting of consecutive integers $\in [1, 2, 3, \ldots, n]$ without any duplicates. You are allowed to swap any two elements. Find the minimum number of swaps required to sort the array in ascending order.

Sorting 시키는데 필요한 swap의 수를 찾는 것으로 문제의 input format은 1부터 $n$까지의 숫자이며 중복이 없이 주어진다. Input format으로 인해 문제가 간단해진다.

Answer

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def minimumSwaps(arr):
    arr_len = len(arr)
    count = 0
    i = 0
    while (i != arr_len - 1):
        i += 1
        if arr[i] == (i + 1):
            continue
        swap_ind = arr[i] - 1
        arr[i], arr[swap_ind] = arr[swap_ind], arr[i]
        count += 1
        i -= 1
    return count

Explanation

꼭 예제의 순서대로 swap을 할 필요는 없다. 우선 배열의 길이와 count, i를 초기화해준다. 아이디어는 간단하다. 처음부터 하나씩 조회하면서 1부터 $n$까지의 수이므로 i+1의 index에 i가 있으면 넘어가고 아니라면 지금 접근하는 수 i를 i+1의 index위치로 보내주는 것이다. 이 때 보내줄 index는 arr[i] - 1이 되며 해당 자리에 있던 수는 지금 조회중인 자리와 위치를 바꾸어준다. (index i와 숫자 i가 혼란스러울 수 있으므로 주의하자)

Index위치가 바뀌었으므로 i-=1을 통해 바뀐위치부터 과정을 반복한다. 이를 위해서 for문을 사용하지 않고 while을 사용해 반복문내에서 사용하는 index i를 조절한다.

Reference

• HackerRank