LeetCodeWeekly 239C 1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number next_permutaion と 隣接swapする回数

題意

• 最大1000桁のある数値$num$が与えられる。いま、この数を並び替えて作れる数字を考えたときに、$num$よりも厳密に大きい数字のみを考える。
• このような$k$番目を考えると、$num$の隣接した数字を最小で何回入れ替えればいいか。

こう考えた

この問題は2つのステップに分かれる。

• STEP1: $k$個大きな数字を求める。これを$target$とする
• STEP2: $num$の隣接数字を何回入れ替えると$target$にできるかを判定する

STEP1 1つ目に大きな数値

C++ならnext_permutationを使う。next_permutaionはhttps://cpprefjp.github.io/reference/algorithm/next_permutation.html
にある。通常は、ソートした配列からスタートして、辞書順にすべての順列を得ることに使われる。ここで、next_permutationは毎回、配列を並び替える。つまり、${1,2,3}$を与えると、配列が${1,3,2}$に並び替えられる。この性質を使い、$nums$を配列として$k$回next_permutaionに渡すことで、$target$を求められる。

STEP2 隣接した要素を並び替える回数

$num$が高々1000桁なので愚直にシミュレーションする。STEP1で元の$nums$は並び替えられてしまうので、これを保持してき、$ind=i$の文字が次に出現する位置$j$を探索して、位置$i$まで実際にswapすればよい。

実装

class Solution {
public:
    int getMinSwaps(string num, int k) {
        int sl = num.size();
        int res = 0, j;
        vector<int> dat(sl), odat(sl);
        REP(i, sl) odat.at(i) = num[i] - 0x30;
        REP(i, sl) dat.at(i) = num[i] - 0x30;
        REP(i, k) next_permutation(dat.begin(), dat.end()); // k個先を探索する
        REP(i, sl){ // すべての文字をチェック
            if(dat[i] == odat[i]) continue; // 入れ替える必要がない
            j = i + 1;
            while(dat[j] != odat[i]) j++; // 文字がある場所jを探す
            while(j > i) { // swapをシミュレーション
                swap(dat[j-1], dat[j]);
                --j;
                ++res;
            }
        }
        return res;
    }
};