Minimum Swaps

def minimumSwaps(arr, n):
    findIndex = 1
    swapCount = 0

    hashNumber = dict((val, idx) for idx, val in enumerate(arr))

    for i in range(0, n):
        if arr[i] == i+1:
            continue
        else:
            foundIndex = hashNumber[i+1]
            hashNumber[i+1], hashNumber[arr[i]] = i, foundIndex
            arr[i], arr[foundIndex] = arr[foundIndex], arr[i]
            swapCount += 1

    return swapCount

 

간단히 문제를 풀면 이중 포문 을 돌면서 자신의 위치에 맞는 값을 찾아서 교환하고 카운팅을 올려주면 된다. 대략 n * n (n-1, n-2, n-3, … 1) => n^2이 나오게 된다. 당연히 Time out 이 나와서 어떻게 풀까 고민했다. 병목이 생기는 부분은 자신의 위치에 맞는 값을 찾는 방식이다.

 

자신의 위치에 맞는 값을 빨리 찾으면 쉽게 해결이 된다.

그래서 각 값의 맞는 인덱스를 매칭 해주는 딕셔너리를 하나 더 만들어서 해결했다. 해당 값이 어느 인덱스에 위치하고 있는지 딕셔너리를 O(1)의 속도를 얻어 올 수 있기 때문에.