해커랭크 minimum swaps 알고리즘
-
[해커랭크 HackerRank] 배열 문제 Minimum Swaps 2[IT] 공부하는 개발자/Algorithms 2019. 10. 30. 21:32
Minimum Swaps 연속하는 자연수로 된 배열을 input으로 주고, 안의 원소들을 서로 교환해서 정렬시킬 때, 가능한 가장 적은 교환 횟수를 구하는 문제이다. [7, 1, 3, 2, 4, 5, 6] 이라는 arr 배열을 입력받았을 때, arr[0] 과 arr[3]를 자리 교환, (i=0 에서 7과 2가 자리를 바꾸었다) arr[0] 과 arr[1]를 자리 교환, ...., 최종적으로 arr[5], arr[6]을 자리 교환하여 [1, 2, 3, 4, 5, 6, 7] 으로 정렬이 완료되었다. 정렬 되기까지의 최소 교환 횟수는 5번으로, 5를 리턴한다. 풀이법 원소가 제 자리에 있는지 확인할 때에는 인덱스로 확인하면 된다. 배열에서 인덱스 i에 대해, i+1 == x[i] 를 만족한다면 그 원소는 제 ..