競技プログラミングをやっていると、末尾の要素を先頭に持ってくるような処理を要求されるシーンはあるのではないでしょうか。
そんな時に使用できる先頭末尾の操作方法について解説します。
先頭末尾の操作ならQueueを使おう
Pythonのリストは、appendは高速で行えますが、pop処理は時間がかかってしまいます。
先頭末尾の操作であれば、それに特化したQueueというデータ型が実装されているのでこれを使用しましょう。
本来、Queueは先頭の取り出しと末尾への追加にのみ特化したアルゴリズムです。しかし、Pythonのdequeは、先頭末尾の追加削除両方に対応しているため、今回のようなケースにも使用可能です。
https://docs.python.org/ja/3/library/collections.html#collections.deque
rotateで一発
>>> from collections import deque
>>> l = list(range(5))
>>> l
[0, 1, 2, 3, 4]
>>> d = deque(l)
>>> d
deque([0, 1, 2, 3, 4])
>>> d.rotate(1)
>>> d
deque([4, 0, 1, 2, 3])これだけだと寂しいので、他の使い方もちょこっと紹介します。
>>> from collections import deque
>>> l = list(range(5))
>>> l
[0, 1, 2, 3, 4]
>>> d = deque(l)
>>> d
deque([0, 1, 2, 3, 4])
# 複数一気に移動させたい時は、その数を引数に入力しましょう
>>> d.rotate(2)
>>> d
deque([3, 4, 0, 1, 2])
# 先頭を末尾に持っていきたい場合は、負数を入力すれば対応しています
>>> d.rotate(-1)
>>> d
deque([4, 0, 1, 2, 3])移動させる要素を見たい場合は、popを使おう
本来、Queueといえばこれ「pop」です。
Queueの右側の要素を取得して、配列から削除する処理です。
これを使うと、移動させる要素を参照しやすくなります。
>>> from collections import deque
>>> l = list(range(5))
>>> l
[0, 1, 2, 3, 4]
>>> d = deque(l)
>>> tmp = d.pop()
>>> print(tmp, "とったどー！") # 任意の処理を行う
4 とったどー！
>>> d
deque([0, 1, 2, 3])
>>> d.appendleft(tmp)
>>> d
deque([4, 0, 1, 2, 3, 4])ライブラリを使わない方法
速度を必要としない場合は、もっと簡単な方法はあります。
それは、配列操作を使用する方法です。速度は、Order(N)となるので、速度を求められる場合は使用出来ないので注意しましょう。
>>> l = list(range(5))
>>> l
[0, 1, 2, 3, 4]
>>> l = l[-1:]+l[:-1]
>>> l
[4, 0, 1, 2, 3]最後の要素1つの配列と最後を除く配列を連結することによって、移動を実現しています。
まとめ 配列の末尾を先頭に移動させる方法
配列の末尾を先頭に移動させる方法について、dequeueを使用する方法と単純な配列操作によるものの2つについて解説しました。
他にもいろいろ解説していく予定なので、良ければ読んでみてください。