[Hackerrank in C] 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

Minimum Swaps 2 | HackerRank

 

풀이:

minimum swap (최적의 바꾸기)를 구하려면 cycle을 파악해야한다.

여기서 cycle이란 index_before -> index_after가 계속 연결된 체인을 말한다.

 

예를 들어, arr = [4,3,1,2] 일때, 

index 0 -> index 3

index 1 -> index 2

index 2 -> index 0

index 3-> index 1 이 되어야한다.

 

이 때, cycle이 생긴다 : 0->3->1->2->0 (cycle size = 4, #swaps = cycle_size -1 = 3).

 

물론 언제나 array에 1개의 cycle이 있지는 않다. 여러개의 cycle을 고려해 visited array로 이미 cycle에 넣은 index를 다시 넣지않게 주의해야한다.

여러개의 cycle이 있을 땐, swaps += cycle_size - 1; 가 된다.

 

코드:

// Complete the minimumSwaps function below.
int minimumSwaps(int arr_count, int* arr) {
    // need to figure out the cycle: [before->after]->[before->after]
    int swaps = 0;
    bool* visited = (bool*)calloc(arr_count, sizeof(bool));
    
    for(int i=0; i<arr_count; i++) {
        if(visited[i]==false) {
            if(arr[i] == i+1) {
                visited[i] = true;
                continue;
            }
        
            int curr = i;
            int cycle_size = 0;
            while(!visited[curr]) {
                visited[curr] = true;
                curr = arr[curr] - 1;
                cycle_size++;
            }
            swaps += (cycle_size - 1);
        }
    }
    return swaps;

}