[HakerRank]Minimum Swaps2_배열 정렬에 필요한 최소 스왑 횟수 구하기

Minimum Swaps 2 [Minimum Swaps Required to Sort an Array]

https://www.hackerrank.com/challenges/minimum-swaps-2/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays

Minimum Swaps 2 | HackerRank

 

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.

무작위로 숫자가 들어가있는 배열을 오름차순으로 정렬하기 위해 필요한 최소의 스왑 횟수를 구하는 문제이다.

 

처음에는 어떤 정렬 알고리즘을 써야 하나 고민을 했는데, 틀린 접근 방법이었다. 

 

우선 주어진 배열의 조건은 1 ~ n 까지 비어있는 값이 없다. 

즉 길이가 10인 배열이 주어지면 해당 배열에는 1 ~ 10까지의 값이 전부 들어있다. 

 

이렇게 된다면 배열의 값은 그 배열의 인덱스로 넣어주면 되는 것이다. 

ex) 2,3,4,1,5 

배열의 첫번째 값 2는 배열의 인덱스 (2-1) 번째로 들어가면 된다. 

 

이걸 깨닫는 순간 이 문제는 끝이다. 

 

다만 시간복잡도를 O(n)으로 코드를 짜는 게 중요하다. 안 그러면 시간 초과로 몇몇 케이스에서는 오답이라고 나온다. 

// Complete the minimumSwaps function below.
    static int minimumSwaps(int[] arr) 
    {
        int len = arr.Length;
        int cnt = 0;

        for(int i=0; i<len; )
        {
            if(arr[i] != (i+1))
            {
                int idx = arr[i]; 
                int temp = arr[idx-1];
                arr[idx-1] = arr[i];
                arr[i] = temp;
                cnt++;
            }
            else
                i++;
        }
        return cnt;
    }

내가 작성한 코드이다. 

 

첫 조건문은 arr[i] 배열 값과 (i+1) 해당 인덱스의 값이 틀리면 참이다. (배열은 0부터 시작이므로 i+1이다)

 

그 후 해당 배열의 값(arr[i])을 그 해당 인덱스 값(arr[arr[i]-1])과 바꿔준다. 

 

이 과정을 반복하면 시간복잡도가 O(n)을 만족하며 문제를 해결할 수 있다.