ゼロから始めるLeetCode Day79「1282. Group the People Given the Group Size They Belong To」

概要

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

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

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

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

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

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day78 「206. Reverse Linked List」

次回
ゼロから始めるLeetCode Day80「703. Kth Largest Element in a Stream」

Twitterやってます。

問題

1282. Group the People Given the Group Size They Belong To
難易度はMedium。

問題としては、0からn - 1までのIDを持つ人がn人存在し、それぞれはちょうど1つのグループに所属しています。各人が所属するグループのサイズを示す長さnの配列groupSizesが与えられた場合、グループの数と、各グループに含まれる人のIDを返します。

任意の解を任意の順番で返すことができ、IDについても同様です。また、少なくとも一つの解が存在することが保証されています。

Example 1:

Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]
Explanation:
Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].

Example 2:

Input: groupSizes = [2,1,3,3,3,2]
Output: [[1],[0,5],[2,3,4]]

＃解法

class Solution:
    def groupThePeople(self, groupSizes):
        ans,group,next_group = [],[],[]
        for i,j in enumerate(groupSizes):
            group.append((j,i))
        group.sort()
        for length,index in group:
            next_group.append(index)
            if len(next_group) == length:
                ans.append(next_group)
                next_group = []    
        return ans
# Runtime: 64 ms, faster than 75.60% of Python online submissions for Group the People Given the Group Size They Belong To.
# Memory Usage: 12.7 MB, less than 59.40% of Python online submissions for Group the People Given the Group Size They Belong To.

最初にgroupSizesのインデックスと値を入れ替え用意したgroupに入れ、ソートします。

そしてソートした長さとインデックスを取得して長さをnext_groupに追加し、毎回groupの長さとnext_groupの長さが同値であるかをチェックし、仮に同値であれば返す予定のansに追加、終了です。

そのansに追加した後にnext_group を初期化しておかないと以下のようになる点に注意してください。

Input
[3,3,3,3,3,1,3]
Output
[[5,0,1,2,3,4,6],[5,0,1,2,3,4,6]]
Expected
[[5],[0,1,2],[3,4,6]]

Acceptanceが高いので何かあるのかと思いましたが、特に何もなかったですね。

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