##1. はじめに
皆さん、初めまして！
今、大学でソフトウェア工学を専攻しているモナ坊です。
読まれる前に、読者にはコードよりも考え方を参考として読んで欲しいという希望があります。
突然ですが、皆さん配列の流れに困惑したことはありますでしょうか？
そのくらい分かるわ！とつっこまれるかも知れませんが、もう少し読んでください。
では、正方形の配列をポインターで渦状に移動させる方法はご存知でしょうか？
詳しく説明致します。
本題
では、さっそく本題に入ります。正方形の二次配列が存在するとします。
例.)
array = [
[1, 2, 3, 4]
[12, 13, 14, 5]
[11, 16, 15, 6]
[10, 9, 8, 7]
]
この 縦x横の二次配列を渦状に一つ一つの要素を渡り、一次配列を取得してください。(時間計算量はO(n))
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
##考え方##
まずは考え方からです。
1. 少し視点を変えて見てみる
1つ目の画像：
１つ目の画像をみるとわかりやすいかも知れません。
渦巻状に取得はするものの、そこで少し視点を変えて問題に取り組んでみると
外側の四角と内側の四角に分けることができます。
そう見てみると少し、複雑さがなくなりました。ね？
次にこの四角を迂回するにあたって、ポインターが2つ（ロウとカラム用）あると考えてください。
ここでのポインターは、簡潔に言うと処理を指示する為に「この処理をここでしてね！」とコンピューターに伝えるためのものと捉えてください。
このポインター２つを渦状に取得させるために考慮する点が１つあります。
それは、二重計上(double counting)の制御です。
補足：
ここでは、ロウは横列、カラムは縦列を指しているます。
二重計上(double counting) は簡潔に言いますと、処理にあたって同じ要素が被ってしまうことです。
2. 二重計上の制御
次の画像をご覧ください。
２つ目：
こうすることによってお互いに境界線を作ることができ、また二重計上も防ぐことができるので効率の良い解き方になってくると思います
*SC, EC, SR, ERとは？？
SCがカラムのはじめ、ECがカラムの終わり
SRがロウのはじめ、ERがロウの終わり
となっています。
##3. 一連の処理の流れ(外側)
それでは、最後に準備が整ったところで流れを説明します。
3.1 トップロウ([1, 2, 3, 4])をカラム用のポインターで取得します
ここは、普段使われているfor loopの仕方でできますね。
サンプルコード：
for col in range(sc, ec + 1):
result.append(array[sr][col])
3.2 ECが指しているカラムをERまでロウ用のポインターで取得します。(ここでは、[5, 6, 7]ですね。）
サンプルコード：
for row in range(sr + 1, er + 1):
result.append(array[row][ec])
3.3 ボトムロウ([10, 9, 8])を逆方向にカラム用のポインターで取得します。
ここは、reverseというbuilt-in function を使って逆方向のfor loop を実装します。 サンプルコード：
for col in reversed(range(sc, ec)):
result.append(array[er][col])
3.4 最後に、２行目の[12]と３行目の[11]を取得したいのでSR+1 ~ ER区間で逆方向にロウ用のポインターで取得します。
ここも、reverse を使います。 サンプルコード：
for row in reversed(range(sr + 1, er)):
result.append(array[row][sr])
これで、やっと外側の四角の要素を全て渦状に取得できました。
##4. 一連の処理の流れ(内側)
次は、内側の四角です。
でも、このまま処理を同じように回すとhard codingになってしまいますね？
なので、SRとSCを１つ足して内側に寄せます。また、ECとERを１つ足して内側に寄せることによって1~5で作ったものを再利用することができます！ECOですね〜笑
#内側の正方形の処理
sr += 1
er -= 1
sc += 1
ec -= 1
以下からは、画像とコードでの説明を省略致します。
-
トップロウ([13, 14])をカラム用のポインターで取得します
こちらも同様に、普段使われているfor loopの仕方でできますね。 -
ECが指しているカラムをERまでロウ用のポインターで取得します。(ここでは、[15]ですね。）
-
ボトムロウ([16])を逆方向にカラム用のポインターで取得します。
ここは、reverseというbuilt-in function を使って逆方向のfor loop を実装します。 -
最後に、SRがERと等しくなるのでrangeが０になり何も取得できないようになります。
完成コード
def spiralTraverse(array):
result = []
sr, er = 0, len(array) - 1
sc, ec = 0, len(array[0]) - 1
while sr <= er and sc <= ec:
for col in range(sc, ec + 1):
result.append(array[sr][col])
for row in range(sr + 1, er + 1):
result.append(array[row][ec])
for col in reversed(range(sc, ec)):
result.append(array[er][col])
for row in reversed(range(sr + 1, er)):
result.append(array[row][sr])
sr += 1
er -= 1
sc += 1
ec -= 1
return result
##終わりに
あくまで、１つの考え方なので、他にも解答方法はいくつもあります。例えば、再帰法を使った処理など。
注意点として、エッジケースをここでは考慮していないのでそこは問題に合わせて対応してください。
長くなりましたが、以上となります！お疲れ様でした！
LGTM よろしくお願いします！