Hackerrank_Lily's Homework_사이클 분할

https://www.hackerrank.com/challenges/lilys-homework/problem

Lily's Homework | HackerRank

 

---

 

조지가 릴리랑 놀고 싶어서 릴리의 숙제를 도와주려한다. 

하지만 숙제는 자기가 알아서 하도록 하자. 

 

알고리즘 끝. 

 

 

 

 

 

 

..그래도 릴리를 도와주도록 하자. 

어떤 배열이 있을 때 최소한으로 숫자를 스왑해서 아름다운 배열로 만들어야 한다. 

 

정렬을 해가며 최소 교환 수를 찾으려는 당신! 

 

이제는 사이클 분할을 사용해보자

 

아름다운 배열은 인접한 숫자의 값이 최소가 되는 배열이다. 

그렇다면 배열은 정렬된 상태여야 할 것이다. 오름차순이 될지 내림차순이 될지는 교환 횟수를 비교해보면 된다.

 

{7, 15, 12, 3} 이 있을 때, 7과 3의 위치를 바꾸고 15와 7의 위치를 바꾸면 2회로 아름다운 배열을 만들 수 있다. 

 

 

사이클 분할에 대해 알아보자.

 

정렬되있는 숫자의 위치와 정렬하지 않은 숫자의 위치를 비교하여 숫자가 정렬이 되기 위해

제자리를 찾아가는 경로가 다시 시작으로 돌아올 때 사이클이 발생했다고 한다. 

 

그래서 배열을 사이클로 나누고 각 사이클마다 최소 교환 횟수를 더하면 그 배열의 최소 교환 횟수를  찾을 수 있따! 

 

사이클에서의 교환 횟수는 사이클의 크기 - 1이 되는데 이는 

{3, 1, 2}가 있을 때, 1->3 교환, 3 -> 2 교환이 필요하다.

한번 교환 할 때마다 하나의 숫자가 제자리를 찾아 감으로 마지막 숫자는 마지막 이전 숫자가 제자리를 찾아가면 

자연스레 마지막 숫자도 제자리를 찾게 된다. 

그래서 사이클에서 교환 횟수는 사이클의 크기 - 1이 되는 것이다. 

 

 

그러면 사이클을 어떻게 찾을 수 있을까! 

이때는 두개의 배열이 필요하다. 

하나는 아직 정렬하지 않은 배열과 다른 하나는 오름차순 혹은 내림차순으로 정렬된 배열이다. 

 

정렬된 배열에는 원래 위치에 대한 정보를 저장해 둔다. 

그리고 정렬하지 않은 배열의 첫번째 요소를 확인하는데 

첫번째 요소의 제자리가 어디인지 확인한다. 

 

{7, 15 ,12, 3}의 예제의 사이클을 찾는 순서를 정리해보자면 아래와 같다. 

1. 현재 첫번째 요소 '7'의 제자리는 idx 1이다. 
2. 현재 idx 1의 자리에는 '15'가 있다. 
3. '15'의 제자리는 idx 3이다. 
4. 현재 idx 3에는 '3'이 있다. 
5. '3'의 제자리는 idx 0이다. 
6. 현재 idx 0에는 '7'이 있다. 
7. '7'으로 시작해 '7'으로 돌아오는 사이클을 찾았다

 

사이클에서 교환 횟수는 사이클의 크기  3 (7, 15, 3)에서 1을 뺀 2가 된다!

이렇게 배열에서 사이클을 찾아 분할하고 각 사이클의 교환 횟수를 더한다. 

그리고 오름차순과 내림차순의 교환 횟수를 비교하여 최소 값을 반환하면 릴리의 숫제를 도울 수 있다. 

 

😶‍🌫️ 코드 보기 🔽

코드!

int minSwapsToSort(vector<int> arr) 
{
    int n = arr.size();
    vector<pair<int, int>> sortedArr(n);
    
    for (int i = 0; i < n; i++) 
    {
        sortedArr[i] = {arr[i], i};
    }

    sort(sortedArr.begin(), sortedArr.end());

    vector<bool> visited(n, false);
    int swapCount = 0;

    for (int i = 0; i < n; i++) 
    {
        if (visited[i] || sortedArr[i].second == i) 
        {
            continue;
        }

        int cycleSize = 0;
        int j = i;

        while (!visited[j]) 
        {
            visited[j] = true;
            j = sortedArr[j].second;
            cycleSize++;
        }

        if (cycleSize > 1) 
        {
            swapCount += (cycleSize - 1);
        }
    }
    return swapCount;
}

int minSwapsToSortDescending(vector<int> arr) 
{
    int n = arr.size();
    vector<pair<int, int>> sortedArr(n);

    for (int i = 0; i < n; i++) 
    {
        sortedArr[i] = {arr[i], i};
    }

    sort(sortedArr.rbegin(), sortedArr.rend());

    vector<bool> visited(n, false);
    int swapCount = 0;

    for (int i = 0; i < n; i++) 
    {
        if (visited[i] || sortedArr[i].second == i) 
        {
            continue;
        }

        int cycleSize = 0;
        int j = i;

        while (!visited[j]) 
        {
            visited[j] = true;
            j = sortedArr[j].second;
            cycleSize++;
        }
        
        if (cycleSize > 1) 
        {
            swapCount += (cycleSize - 1);
        }
    }
    return swapCount;
}

int lilysHomework(vector<int> arr) 
{
    int ascSwaps = minSwapsToSort(arr);
    int descSwaps = minSwapsToSortDescending(arr);

    return min(ascSwaps, descSwaps);
}

 

 

끄읏!