[HackerRank] Minimum Swaps 2 풀이

문제

You are given an unordered array consisting of consecutive integers  [1, 2, 3, ..., 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.

www.hackerrank.com/challenges/minimum-swaps-2

풀이 과정

1. 문제 해석 오류 : 집합 기호와 영어 해석이 잘못됐다. 배열이 1 부터 n까지의 원소라는 의미인데, 1 부터 포함되어야한다는 의미를 놓치고 말았다. n~m에 해당하는 케이스도 정렬하겠다고 열심히 돌렸다. 시간 초과로 일부 submission이 실패했다.

def minimumSwaps(arr):
    min_val = min(arr)
    min_pos = 0
    swap_count = 0
    
    for a in range(len(arr)):
        if min_val == arr[a]:
            min_val += 1   
        else:
            for i in range(a, len(arr)):
                if min_val == arr[i] and arr[a] != arr[i]:
                    arr[a], arr[i] = arr[i], arr[a]
                    swap_count += 1
                    min_val += 1
                    break
    return swap_count

2.  무조건 1부터 라는 조건을 인지한 다음, 현재 값이 i+1 과 같은지 비교해야한다는 것은 알겠다. 그럼 뭐랑 비교한다는 말인가?

3. 답은 현재 값이 i+1이 아닌 경우, 현재 값이 원래 있어야하는 위치로 swap하는 것이다. 중요한 점은, swap 나서 그 자리에 변경된 값을 다시 확인해야한다. 그래서 while을 쓴다.

def minimumSwaps(arr):
    swap_count = 0
    for i in range(len(arr)):
        while(True):
            if arr[i] != i + 1:
                swap_idx = arr[i]
                arr[i], arr[swap_idx - 1] = arr[swap_idx - 1], arr[i]
                swap_count += 1
            else:
                break
    return swap_count

 

답을 내고 나면 항상 바보가 된 기분이다..! 😂