LeetCodeの問題を解いてみた

みなさんこんにちは！
スペースマーケットエンジニアのreyです。

新年あけましておめでとうございます！
今年もどうぞよろしくお願いいたします〜！

今回は、LeetCodeというサイトの問題にチャレンジしてみたので、ご紹介いたします。

LeetCodeってなに?

海外のテック企業などのコーディング面接で使われたり、出題されたものに似ている問題を解くことができる学習サイトのことです。日本よりも主に海外の学生さんが勉強用に結構使っているようです。

https://leetcode.com/

日本だと、AtCoderのようなサービスに少し近いかもしれません！

https://atcoder.jp/?lang=ja

なんで解いてみたの?

エンジニアとしてスキルを少し伸ばせないかなと思っていた時に、牛尾剛さんの「世界一流エンジニアの思考法」という本を読み、そこでプログラミングスキルを上げる方法としてLeetCodeが紹介されていたので、解いてみることにしました。

Spiral Matrix II

興味を持って下さったみなさんに雰囲気を知って頂けたらと思い、難易度中（Medium）レベルの問題を解いてみます。今回は「Spiral Matrix II」という問題をチョイスしました。

内容

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.

問題は英語ですが、大丈夫です。私たちには「Google翻訳」があります。
「Google翻訳」と、入出力の例を見れば、（たぶん）内容が分かります。

nという数値が与えられるので、n * n のマトリクス図を作成して、外側から螺旋状にぐるぐると数値を入れていき、その結果を二次元配列で値を出して下さい、という内容です。

回答する言語も、好きな言語を選べます。Pythonを選択される方が多いと思いますが、弊社はRubyを使用しているので、勉強も兼ねてRubyを選択しました。

解いてみた

最初に自分で考えた方法では、少し時間がかかってしまいました。

法則性を見つけるのが重要だと思ったため、マス目ごとの二次元配列の値を書き出してみました。ポインタは4辺をぐるぐる回転するので、4列ごとに周期がありそうだと考えて、なにか法則性がないかを考えてみました。

結果は、そこまで綺麗な法則性を持ったコードにはならなかったです...
一応クリアしたのですが、コードはあまり綺麗ではないので、ここでは伏せておきます（笑）

最適な解法

シンプルなコードの解法がありましたので、ご紹介します。

1. 最初にマトリクス図を作成する
2. ポインタを移動させて、二次元配列に数値を入れていく
3. ポインタが四隅の角に来たタイミングで、ポインタをターンさせる（二次元配列に入れる増減数値を切り替える）

def generate_matrix(n)
  arr = Array.new(n){ Array.new(n) }
  i, j, di, dj = 0, 0, 0, 1
  (0...n*n).each do |k|
    arr[i][j] = k + 1 
    di, dj = dj, -di if arr[(i+di)%n][(j+dj)%n]
    i += di
    j += dj
  end
  arr
end

まずはじめに、マトリクス図を作ります。

arr = Array.new(n){ Array.new(n) }

順番にマス目に数値を入れていきます。

arr[i][j] = k + 1

ポインタが四隅の角に来たタイミングで、ポインタをターンさせます。

di, dj = dj, -di if arr[(i+di)%n][(j+dj)%n]

A辺をポインタが移動している時：二次元配列[x, y]の y に +1 していく
B辺をポインタが移動している時：二次元配列[x, y]の x に +1 していく
C辺をポインタが移動している時：二次元配列[x, y]の y に -1 していく
D辺をポインタが移動している時：二次元配列[x, y]の x に -1 していく

ポインタが隅っこに到達したタイミングで、arr[(i+di)%n][(j+dj)%n]に値が入ってくるので、そのタイミングで+1, -1の切り替えをしています。
+1, -1の切り替えを1文で綺麗に表現していて、シンプルで無駄のない美しいコードですね...!!

解いてみた感想

今回解いてみた問題は、法則性を見つけるというより、素直に値を入れていく方法が正解の解法でした。アルゴリズムの問題はときどき、パズルのような問題があるので、面白いです。

LeetCodeには、1000問以上の問題が掲載されています。
配列で何度も回していた箇所が、実は1回のループで済む方法があった、など
優秀なエンジニアの方がより効率の良い解法を紹介されているので、学びがあります。

今回は計算量はそこまで問題になりませんでしたが、問題によっては、実行時間がかかり過ぎるとtimeoutでクリアとならないものもあります。（特にRubyは...笑）

まだ自分のスキルに変化があったかどうかは分からないですが、
これからも、気が向いたらLeetCodeの問題にチャレンジしてみようと思います！

最後に

スペースマーケットでは一緒に働く仲間を募集しています！
新しい技術に興味がある方も、手を上げればチャレンジできる環境だと思います。
カジュアルに話を聞きたいだけという方でも大歓迎ですので、ちょっとでも興味があれば
こちらからご応募をお待ちしております！