Hackerrank - Minimum Swaps2

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

불러오는 중입니다...

 

이번 문제는 주어진 배열을 정렬하기 위해 필요한 최소의 swap 수를 구하는 것입니다.

[4, 3, 2, 1]이란 배열이 주어진다면, 이 배열을 [1,  2 3, 4]로 정렬하기 위해 필요한 swap의 수를 구하면 됩니다.

이 때, swap은 아무 위치에 있는 숫자끼리도 바꿀 수 있습니다.

위의 예를 보면,

 

[4,1] swap → [1, 3, 2, 4]

[3,2] swap → [1, 2, 3, 4]

 

따라서 위의 배열을 정렬하는데 필요한 최소의 swap 수는 2입니다.

 

1. 방법

  1) for loop에 enumerate 함수를 사용하여 idx, 숫자를 순차적으로 뽑아냅니다.

  2) 만약 idx와 숫자(x)가 일치하지 않는다면(정렬되어있지 않다는 뜻), 해당 숫자(x)의 고유 idx 위치에 숫자(x)를 입력합니다.(일치하면 for loop 지속)

  3) swap 횟수를 1을 더해줍니다.

  4) x의 고유idx에 존재하던 숫자(y)와 y의 고유 idx에 있는 숫자 z를 비교하고, 다르다면 swap한 뒤 swap 횟수에 1을 더합니다.(같아질 때까지 반복하고, 같다면 swap 횟수에 1을 빼고 for loop로 복귀합니다.) 

  5) for loop이 완료될 때까지 (2) - (4)를 반복한다.

 

* 이 때 for loop 복귀 전에 swap 횟수를 1을 빼주는 이유는, 위에서 주어진 예시[4,3,2,1]에서의 [1,4], [3,2]와 같이 한번 swap을 통하여 두 숫자가 제자리를 찾아가는 경우가 있습니다. 하지만 이 알고리즘에서는 해당 경우를 즉각적으로 검출해내지 못하므로, 1을 빼주는 것입니다.

 

Ex) Input : [4, 3, 2, 1] (이 때 보기 쉽게 idx는 1, 2, 3, 4로 지정하겠습니다. 실제로는 0, 1, 2, 3)

 

for idx, num in enumerate(Input):

→ idx = 1, num = 4

→ idx != num이므로 4가 있어야 할 원래 위치(idx : 4)에 4를 입력하고, num을 1로 바꿔줍니다. [swap 횟수 = 1]

→ [4, 3, 2, 4], num = 1

→ num(=1)이 있어야할 원래 위치(idx : 1)의 숫자(=4)와 num(=1)을 비교합니다.

→ num(=1)이 있어야할 원래 위치(idx : 1)에 num을 입력하고, num을 4로 바꿔줍니다. [swap 횟수 = 2]

→ num(=4)이 있어야할 위치에 해당 숫자(4)가 위치해 있으므로 for loop을 벗어납니다.

 

이상 끝-!