Minimum Swaps 2 - HackerRank
Minimum Swaps 2
- 가장 적게 swap을 해서 오름차순 정렬을 하는 문제 (최소 swap count)
Sample Input
4
4 3 1 2
Sample Output
3
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Minimum_Swaps_2 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int cnt = Integer.parseInt(br.readLine());
int[] arr = new int[cnt];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0 ; i < cnt ; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
int result = Minimum_Swaps(arr);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
bw.write(String.valueOf(result));
bw.flush();
bw.close();
br.close();
}
static int Minimum_Swaps(int[] arr){
int swap_cnt = 0;
for(int i = 0 ; i < arr.length; i++){
for(int j = i ; j < arr.length; j++){
if(i+1 == arr[i]){
break;
}
if(i+1 == arr[j]){
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
swap_cnt += 1;
break;
}
}
}
return swap_cnt;
}
}
참고 사이트
HackerRank : https://www.hackerrank.com/