[해커랭크] Minimum Swaps 2 (C++)

문제 링크: www.hackerrank.com/challenges/minimum-swaps-2/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays

Minimum Swaps 2 | HackerRank

1. 주의할 점

- O(N^2)이 발생하지 않도록 한다

 

2. 구현

- 현재 위치에 맞는 값이 들어있는 경우 다음 값을 확인한다

- 맞는 값이 들어 있지 않은 경우, 현재 위치에 있는 값 Num과 Arr[Num-1]의 값을 스왑한다(배열의 번호는 0부터 시작하기 때문에 -1)

- 스왑했다면, 스왑횟수 Cnt++를 수행하고, 스왑된 값이 정상값이 아닐수도 있으므로 다시 한번 확인하기 위해 i--한다

int minimumSwaps(vector<int> arr) {
    int cnt=0;
    for(int i=0;i<arr.size()-1;i++){
        int num = arr[i];
        if(i==num-1) continue;
        int a = arr[num-1];
        arr[num-1] = num;
        arr[i] = a;
        cnt++;
        i--;
    }
    return cnt;
}