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

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

その対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。

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

Leetcode

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day45 「1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree」

今はTop 100 Liked QuestionsのMediumを解いています。
Easyは全て解いたので気になる方は目次の方へどうぞ。

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)とほとんど一緒でびっくりしました。

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