Minimum Swaps 2

🔗 문제 링크

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

❔ 문제 설명

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.

Example

arr = [7,1,3,2,4,5,6]

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.

minimumSwaps has the following parameter(s):

• int arr[n]: an unordered array of integers

Returns

• int: the minimum number of swaps to sort the array

Input Format

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

⚠️ 제한사항

• $1 ≤ n ≤ 10^5$

• $1 ≤ arr[i] ≤ n$

---

💡 풀이 (언어 : Java)

열심히 풀었지만 시간복잡도 케이스 4개에서 불합격 판정을 받았다. 타인의 풀이를 보았는데 단순한 배열로 전체를 탐색하는 풀이였다. 내가 한 풀이는 리스트를 쓰긴하지만 중간에 전체 탐색을 안하고 끝내는 로직들이 들어있는데 어떻게 내 풀이가 더 느린건지는 아직도 이해가 안간다; 배열을 리스트로 바꿔주는 과정들이 오래걸리는 건가?

내 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;

public class Main {
	private static int minimumSwaps(int n, Integer[] arr) {
		int count = 0;
		Integer[] sortedArr = arr.clone();
		Arrays.sort(sortedArr);
		LinkedList<Integer> arrList = new LinkedList<Integer>(Arrays.asList(arr));
		LinkedList<Integer> sortedList = new LinkedList<Integer>(Arrays.asList(sortedArr));
		for (int k = 1; !arrList.equals(sortedList); k++) {
			int minidx = arrList.indexOf(k);
			if (minidx != 0) {
				arrList.set(minidx, arrList.getFirst());
				count += 1;				
			}
			arrList.poll();
			sortedList.poll();
		}
		return count;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		Integer[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).boxed()
				.toArray(Integer[]::new);
		System.out.println(minimumSwaps(n, arr));
	}
}

배운 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
      static int minimumSwaps(int n, int[] arr) {
        int swapCnt = 0, tmp, idx = 0;
        for(int i = 0; i < n; i++) {
            if(arr[i] != i + 1) {
                for(int j = i + 1; j < n; j++) {
                    if(arr[j] == i + 1) {
                        idx = j; 
                        break;
                    }
                }
                tmp = arr[i];
                arr[i] = arr[idx];
                arr[idx] = tmp;
                swapCnt++;
            }
        }
        return swapCnt;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        System.out.println(minimumSwaps(n, arr));
    }
}