親子関係になってるクラスの1次元配列をいい感じネストさせる

多分プロコンの人からすると
息をするように解決できる単純な問題だと思うけど、割と勉強になったのでメモ
(ソースコードはjavaです)

データベースから取得したデータが下記のクラスの
インスタンスのリストであった場合

それを下記のクラスにマッピングしたい。

もう少し具体的に書くと

こういうデータをデータベースから取得したときに
以下のデータにマッピングしたい


最初に僕が書いたもの

自分自身を生成して、受け取った配列の中から子供を
親として再帰的に関数を呼び出す。

多分計算量はO(log n)


同期のプロコン勢にアドバイス求めてみた

一応欲しい結果は取得できていたんだけど、単純に再帰読みづらいのと、
もっと当たり前な方法があるのかなーと思って聞いてみました。

最初にROOTという全てのItemの親になるダミーを入れているのがミソ。
これによって、最上位の親とそれ以下の子を等価に扱うことができる。

あとはこれだけ

記述はシンプルだし、計算量は O(2n)

僕が予想していない解法がきたので 僕は再帰しか思いつかなかったんだけど、この解法に至るにはどういうポイントがありますか? と聞いてみたところ

多分、今回のはトップダウン的な考え方をボトムアップ的考え方に変えられるなら、思いつきやすいのかも?
トップダウンだと、親につながる子を探すための余計なループが入ってしまったりするけど、
ボトムアップだと、子からつながる親っていうのがただ一つだから、処理を単純化できる、
みたいな感じ?

というアドバイスをいただきました。なるほど納得。。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です