Minimum Swaps 2

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

New Year Chaos | HackerRank

 

• 문제

  • 

    문제

  • 숫자들이 정렬되어 있지 않은 상태로 있을 때, 해당 숫자를 정렬하기 위해서는 최소한 몇 번을 연산이 필요한지 계산 

---

풀이

• 여기서 가장 핵심은 1 ~ n 까지 값이 중복되지 않게 arr에 있다는 것인데, 이는 n 번째 숫자는 반드시 n-1 index위치에 존재해야 한다는 뜻이다
  
  • 경우 1 : arr[i] 요소가 i+1 값이 아닐 경우
    
    • arr [i] - 1 번째 위치의 값과 SWAP 해준다 -> arr [i]-1 위치의 값은 정렬이 된 것이다.
  • 경우 2 : arr [i] 요소가 i+1 값일 경우 i값을 증가시켜준다

•  static int minimumSwaps(int[] arr) {
     int answer = 0;
     //arr은 1~n까지 중복되지 않게 값이 존재하므로 n번째 값은 무조건 n-1인덱스에 위치해야 된다.
     for(int i=0;i<arr.length;){ 
     	if((i+1) != arr[i]){//arr[i]번째 요소가 i+1값이 아니면 SWAP
     		int tmp = arr[i];
    	 	arr[i] = arr[tmp-1];
     		arr[tmp-1] = tmp;
     		answer++;//SWAP 횟수 증가
     	}else{//arr[i] 번째 요소가 i+1 이 될때까지 Swap 을 한다.
    		 i++;
     	}
     }
  
    return answer;
  
  }