950. Reveal Cards In Increasing Order の解き方メモ

次の手順を繰り返す。その結果、公開されたカードのが昇順にソートされているような山札を求めなさい。

1. 山札の一番上のカードを取り除き、そのカードを公開する
2. 山札にカードが残っているとき、山札の一番上のカードを山札の一番下に置く
3. 山札にカードが残っている場合、1.に戻る。そうでない場合、処理を停止する

問題を要約すると、おおよそ上記の通りになります。

---

たとえばABCDEFGの7枚の山札に対し、指定した手順を実施します。

#	山札	公開されたカード
1	ABCDEFG
2	CDEFGB	A
3	EFGBD	AC
4	GBDF	ACE
5	DFB	ACEG
6	BF	ACEGD
7	F	ACEGDB
8		ACEGDBF

最終結果ACEGDBFが昇順にソートされていればよいわけです。Example1を例に考えてみると、ACEGDBFと[2,3,5,7,11,13,17]がイコールになります。わかりやすくマッピングしたものが以下です。

山札	Example1
A	2
B	13
C	3
D	11
E	5
F	17
G	7

求めるのは山札ABCDEFGなので、Example1の答えは[2,13,3,11,5,17,7]になります。

---

上記の手順を要約するとおおよそ以下の通りになります

1. deckと同じ枚数の山札を作成し、指定された手順をシミュレーション
2. シミュレーション結果とソート済みのdeckをマッピングし、山札を再現する

これをそのまま実装すればよいです。

use std::collections::{HashMap, VecDeque};

impl Solution {
    pub fn deck_revealed_increasing(deck: Vec<i32>) -> Vec<i32>  {
        // deckと同じ枚数の山札を作成し、指定された手順をシミュレーション
        let simu_start = (0..deck.len()).collect::<Vec<_>>();
        let mut simu_deck = VecDeque::from_iter(&simu_start);
        let mut simu_cards = Vec::new();
        loop {
            simu_cards.push(simu_deck.pop_front().unwrap());
            if let Some(card) = simu_deck.pop_front() {
                simu_deck.push_back(card);
            } else {
                break;
            }
        }

        // シミュレーション結果とソート済みのdeckをマッピングし、山札を再現する
        let mut sorted_deck = deck;
        sorted_deck.sort();
        let mapper = simu_cards.iter().zip(sorted_deck).collect::<HashMap<_, _>>();
        simu_start.iter().map(|simu_card| mapper[&simu_card]).collect()
    }
}