ゼロから始めるLeetCode Day46「406. Queue Reconstruction by Height」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
[ゼロから始めるLeetCode Day45 「1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree」
次回
ゼロから始めるLeetCode Day47 「14. Longest Common Prefix」

Twitterやってます。

問題

406. Queue Reconstruction by Height

難易度はMedium。
Top 100 Liked Questionsからの抜粋です。

待ち行列に立っている人のランダムなリストがあるとします。
それぞれの人は整数のペア、(h,k)で構成されており、hは人の高さ、kはその人の前にいてh以上の高さを持つ人の人数を指します。

この問題では与えられた待ち行列を再構成するようなアルゴリズムを設計します。

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

解法

二つの整数についてしっかりと整理し、的確にアルゴリズムを組むことが求められる良い問題です。

こういった問題の場合はやはり問題を細かく分割し、それぞれの処理を独立させて考えた方が分かりやすくなると思います。

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        if not people: return []
        dic, height, res = {}, [], []
        for i in range(len(people)):
            p = people[i]
            if p[0] in dic:
                dic[p[0]] += (p[1], i),
            else:
                dic[p[0]] = [(p[1], i)]
                height += p[0],
        height.sort()
        for h in height[::-1]:
            dic[h].sort()
            for p in dic[h]:
                res.insert(p[0], people[p[1]])
        return res
# Runtime: 88 ms, faster than 99.14% of Python3 online submissions for Queue Reconstruction by Height.
# Memory Usage: 14.3 MB, less than 5.88% of Python3 online submissions for Queue Reconstruction by Height.

めちゃ速い！
よくよくdiscuss調べてみたら[これ]
(https://leetcode.com/problems/queue-reconstruction-by-height/discuss/89345/Easy-concept-with-PythonC%2B%2BJava-Solution)とほとんど一緒でびっくりしました。

今回はここまでです。お疲れ様でした。