[HackerRank] Minimum Swap2

1. Problem

• https://www.hackerrank.com/challenges/magic-square-forming/problem

2. Feedback

• array 가 연속적인 것이 아님. 문제 잘못된듯
• brute force 로 풀면 앞에서부터 마지막까지 비교해서 정렬시킴. 복잡도 - O(n2))
• 최적화 작업
  • 메모리를 이용해서 값이 같으면, count 하고, swap 시킴. 이 방법은 모든 값을 비교하지 않고, 가지치기 하기에 그나마 비교횟수가 떨어짐.

3. Source

public class MinimumSwaps2
{
 public static void main(String [] args)
 {
  Scanner in = new Scanner(System.in);
  int n = in.nextInt();
  int arr[] = new int [n];
  for (int i = 0; i < n; i++)
   arr[i] = in.nextInt();
  System.out.println(solve(arr));
 }

 public static int solve(int arr[])
 {
  int arrLength = arr.length;
  int swapCount = 0;
  int copyArr[] = arr.clone();
  Arrays.sort(copyArr);
  for (int i = 0 ; i < arrLength ; i++)
  {
   if (arr[i] != copyArr[i])
   {
    swapCount++;
    for (int j = i + 1 ; j < arrLength ; j++)
    {
     if (arr[j] == copyArr[i])
     {
      int temp = arr[j];
      arr[j] = arr[i];
      arr[i] = temp;
      break;
     }
    }
   }
  }
  return swapCount;
 }
}