1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number.cpp

🔑

1. next_permutation STL을 활용하여, 주어진 수 다음의 최소값을 찾는다.

2. swap 횟수를 찾는다.

  1) 주어진 값과, wonderful number값 두개를 일렬로 놓는다.

  2) 각 자리수를 비교( i , j ) 하며, 같은 값을 찾을 때 까지, 주어진 값의 index를 이동( j-- )시킨다.

  3) 이동된 index에 해당하는 값( org[j] )이, wonderful[i]와 같을 때 까지, swap한다. swap횟수만큼 res++

 

class Solution {
public:
    int getMinSwaps(string num, int k) {
        int res =0;
        string org = num;
        for(int i =0; i<k;i++){
            next_permutation(num.begin(), num.end());
        }
        
        for(int i =org.size()-1; i>=0; i--){
            int j = i;
            while(num[i]!=org[j])j--;
            for(int l = j; l<i; l++){
                swap(org[l],org[l+1]);
                res++;
            }
        }
        return res;
    }
};