【Python】カードが昇順にめくれるように配置するプログラムの書き方

カードの山が与えられ、それをめくったときに昇順で現れるような初期配置を求める問題を考えてみましょう。

カードがめくられるルール

1. 一番上のカードを取り除いて表向きにし、その直後のカードは一番後ろへ移動させる。
2. 手順1を、カードがなくなるまで繰り返す。

この操作を行ったとき、めくられたカードの並びが昇順となるような配置を求めるのが目的です。

入力例と動作のシミュレーション

たとえば、入力が cards = [1, 2, 3, 4, 5, 6, 7, 8] の場合、出力は [1, 5, 2, 7, 3, 6, 4, 8] となります。

• 1 を取り除き、5 を一番後ろへ移動 → 現在の状態：[2, 7, 3, 6, 4, 8, 5]
• 2 を取り除き、7 を一番後ろへ移動 → 現在の状態：[3, 6, 4, 8, 5, 7]
• 3 を取り除き、6 を一番後ろへ移動 → 現在の状態：[4, 8, 5, 7, 6]
• 4 を取り除き、8 を一番後ろへ移動 → 現在の状態：[5, 7, 6, 8]
• 5 を取り除き、7 を一番後ろへ移動 → 現在の状態：[6, 8, 7]
• 6 を取り除き、8 を一番後ろへ移動 → 現在の状態：[7, 8]
• 7 を取り除く → 残りは [8] のみ
• 最後に 8 を取り除いて終了

解法のアプローチ

この問題は、実際の操作を逆算するのではなく、どの位置のカードが何番目にめくられるかを先に求めることで解けます。手順は以下の通りです。

1. リスト cards をソートします。
2. idx：0 から cards の長さまでの連番リストを作成します。
3. order：新しい空のリストを用意します。
4. q：キュー（両端キュー）を作成し、idx の要素をすべて挿入します。
5. q が空でない限り、次の処理を繰り返します。
   • q の先頭要素を取り除き、order に追加する。
   • q が空でなければ、さらに先頭要素を取り除いて末尾へ追加する。
6. ans：cards と同じサイズのリストを作り、すべて 0 で初期化します。
7. order の各インデックス i と cards の各値 card について、ans[i] = card を設定します。
8. ans を返します。

ここでは、collections.deque（両端キュー）を使うことで、先頭からの取り出しと末尾への追加を効率的に行えます。

実装例

from collections import deque
class Solution:
    def solve(self, cards):
        cards.sort()
        idx = [i for i in range(len(cards))]
        order = []
        q = deque(idx)
        while q:
            order.append(q.popleft())
            if q: q.append(q.popleft())
        ans = [0 for _ in cards]
        for i, card in zip(order, cards):
            ans[i] = card
        return ans
ob = Solution()
print(ob.solve([1, 2, 3, 4, 5, 6, 7, 8]))

入力

[1, 2, 3, 4, 5, 6, 7, 8]

出力

[1, 5, 2, 7, 3, 6, 4, 8]

この方法なら、計算量は O(n log n)（ソート部分が支配的）に抑えられ、カードの枚数が多くても効率的に正しい配置を求められます。