[HackerRank] Arrays: Minimum Swaps 2 (Python)

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. You need to find the minimum number of swaps required to sort the array in ascending order.

For example, given the array arr = [ 7, 1, 3, 2, 4, 5, 6, ] we perform the following steps:

i   arr                     swap (indices)
0   [7, 1, 3, 2, 4, 5, 6]   swap (0,3)
1   [2, 1, 3, 7, 4, 5, 6]   swap (0,1)
2   [1, 2, 3, 7, 4, 5, 6]   swap (3,4)
3   [1, 2, 3, 4, 7, 5, 6]   swap (4,5)
4   [1, 2, 3, 4, 5, 7, 6]   swap (5,6)
5   [1, 2, 3, 4, 5, 6, 7]

It took 5 swaps to sort the array.

 

Function Description

Complete the function minimumSwaps in the editor below. It must return an integer representing the minimum number of swaps to sort the array.

minimumSwaps has the following parameter(s):

• arr: an unordered array of integers

Input Format

The first line contains an integer, n, the size of arr.
The second line contains n space-separated integers arr[ i ].

 

Constraints

• 1 <= n <= 10^5
• 1<= arr[ i ] <= n

Output Format

Return the minimum number of swaps to sort the given array.

 

Sample Input 0

4
4 3 1 2

Sample Output 0

3

Explanation 0

Given array arr : [ 4, 3, 1, 2 ]
After swapping ( 0, 2 ) we get arr : [ 1, 3, 4, 2 ]
After swapping ( 1, 2 ) we get arr : [ 1, 4, 3, 2 ]
After swapping ( 1, 3 ) we get arr : [ 1, 2, 3, 4 ]
So, we need a minimum of 3 swaps to sort the array in ascending order.

 

Sample Input 1

5
2 3 4 1 5

Sample Output 1

3

Explanation 1

Given array arr : [ 2, 3, 4, 1, 5 ]
After swapping ( 2, 3 ) we get arr : [ 2, 3, 1, 4, 5 ] 
After swapping ( 0, 1 ) we get arr : [ 3, 2, 1, 4, 5 ]
After swapping ( 0, 2 ) we get arr : [ 1, 2, 3, 4, 5 ]
So, we need a minimum of 3 swaps to sort the array in ascending order.

 

Sample Input 2

7
1 3 5 2 4 6 7

Sample Output 2

3

Explanation 2

Given array arr : [ 1, 3, 5, 2, 4, 6, 7 ]
After swapping ( 1, 3 ) we get arr : [ 1, 2, 5, 3, 4, 6, 7 ]
After swapping ( 2, 3 ) we get arr : [ 1, 2, 3, 5, 4, 6, 7 ]

After swapping ( 3, 4 ) we get arr : [ 1, 2, 3, 4, 5, 6, 7 ]
So, we need a minimum of 3 swaps to sort the array in ascending order.

 

첫번째 시도

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the minimumSwaps function below.
def minimumSwaps(arr):
    sorted_arr = sorted(arr)
    answer = 0

    for i in range(len(arr)-1):
        min_num = min(arr[i+1:])
        if sorted_arr == arr:
            break
        if arr[i] > min_num:
            index = arr.index(min_num)
            temp = arr[i]
            arr[i] = arr[index]
            arr[index] = temp
            answer = answer + 1
    return answer

먼저 입력받은 arr를 바탕으로 정렬된 arr를 하나 생성해주고

arr을 처음부터 탐색하면서

현재 인덱스의 값과 현재 인덱스의 다음 인덱스부터 마지막 인덱스까지의 값들 중에 가장 최소값을 비교하여

현재 인덱스의 값이 크면 두 값의 위치를 서로 바꾸어줍니다.( swap해줍니다 )

반복문을 돌때 아까 정렬해둔 arr와 정렬을 하고 있는 arr가 동일해지면 반복문을 중단합니다.

 

결과

Time Limit에 걸렸습니다.

 

두번째 시도

뭔가 sorted메소드와 min메소드를 호출할 때 시간이 오래걸리는 것 같아 두 메소드를 제외하고

arr[ i ] 의 값이 i + 1 이어야함을 바탕으로 다시 만들어보았습니다.

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the minimumSwaps function below.
def minimumSwaps(arr):
    answer = 0

    for i in range(len(arr)):
        while(arr[i] != i+1):
            temp = arr[i]
            arr[i] = arr[temp-1]
            arr[temp-1] = temp
            answer = answer + 1
    return answer

결과

 

SOMJANG/CODINGTEST_PRACTICE