ゼロから始めるLeetCode Day2 「2225. Find Players With Zero or One Losses」

概要

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

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

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

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

LeetCode

未経験のエンジニアなので、基本的に簡単なもの（easyでacceptanceが高い順）から解いていきます。

問題

2225. Find Players With Zero or One Losses

問題としては、プレイヤー同士の勝敗が格納された配列がわたされるので、1回も負けていないプレイヤーリストと1回負けたプレイヤーリストに分けて出力するもの。

例1:
入力：matches(左winner, 右loser) = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
出力：[[1,2,10],[4,5,7,8]]
説明：
プレイヤー1、2、10は1試合も負けていない。
プレイヤー4、5、7、8はそれぞれ1勝1敗。
プレイヤー3、6、9はそれぞれ2敗している。
したがって、解答は[[1,2,10], [4,5,7,8]]となる。

例2:
入力：matches(左winner, 右loser)= [[2,3],[1,3],[5,4],[6,4]]
出力： [[1,2,5,6],[]]
説明：
プレイヤー1、2、5、6はどの試合にも負けていない。
プレイヤー3と4はそれぞれ2敗している。
したがって、解答は[[1,2,5,6], []]となる。

制約条件:
・1 <= matches.length <= 105
・matches[i].length == 2
・1 <= winner[i], loser[i] <= 105
・winner[i] != loser[i]
・All matches[i] are unique.

回答

class Solution:
    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
        losses = defaultdict(int)
        all_players = set()

        for winner, loser in matches:
            losses[loser] += 1
            all_players.add(winner)
            all_players.add(loser)

        no_loss = []
        one_loss = []

        for player in sorted(list(all_players)):
            if losses[player] == 0:
                no_loss.append(player)
            elif losses[player] == 1:
                one_loss.append(player)

        return [no_loss, one_loss]

解説

1.初期化

losses = defaultdict(int)
all_players = set()

losses = defaultdict(int)
各プレイヤーの敗北数を記録するための辞書を作成する。
※defaultdict（）：辞書を作成する。キーが存在しない場合に、デフォルト値を割り当てる。
（この場合はint型のデフォルトである0を自動的に割り当てる。）

all_players = set()
試合に参加したすべてのプレイヤーのIDを格納するためのセット。
セットを使用すると、重複するプレイヤーIDが自動的に排除される。

2.試合結果の処理

for winner, loser in matches:
    losses[loser] += 1
    all_players.add(winner)
    all_players.add(loser)

for winner, loser in matches:
matchesリスト内の各試合（[winner, loser]）を順番に処理する。

losses[loser] += 1
試合で負けたプレイヤー（loser）の敗北数を記録・更新する。

all_players.add(winner)
これまでに登場したすべてのプレイヤーを追加する。

all_players.add(loser)
上記と同様に、これまでに登場したすべてのプレイヤーを追加する。

※all_playersは次のfor文使用する。

例

入力：matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]

試合 (winner, loser)	lossesの更新	all_playersの更新
[1, 3]	losses[3] = 1	{1, 3}
[2, 3]	losses[3] = 2	{1, 2, 3}
[3, 6]	losses[6] = 1	{1, 2, 3, 6}
[5, 6]	losses[6] = 2	{1, 2, 3, 5, 6}
[5, 7]	losses[7] = 1	{1, 2, 3, 5, 6, 7}
[4, 5]	losses[5] = 1	{1, 2, 3, 4, 5, 6, 7}
[4, 8]	losses[8] = 1	{1, 2, 3, 4, 5, 6, 7, 8}
[4, 9]	losses[9] = 1	{1, 2, 3, 4, 5, 6, 7, 8, 9}
[10, 4]	losses[4] = 1	{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
[10, 9]	losses[9] = 2	{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

このループが終了すると、losses と all_players は以下のようになる。

• losses: {3: 2, 6: 2, 7: 1, 5: 1, 8: 1, 9: 2, 4: 1}
• all_players: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

3.結果リストの初期化

no_loss = []
one_loss = []

no_loss = []
敗北経験のないプレイヤーを格納するリスト。

one_loss = []
ちょうど1回敗北したプレイヤーを格納するリスト。

4.プレイヤーごとの敗北数の分類

for player in sorted(list(all_players)):
    if losses[player] == 0:
        no_loss.append(player)
    elif losses[player] == 1:
        ne_loss.append(player)

return [no_loss, one_loss]

for player in sorted(list(all_players)):all_playersの要素をソートして、リストに変換し、各プレイヤーについて処理を行う。

if losses[player] == 0:
no_loss.append(player)
プレイヤーの敗北数が0回である場合、そのプレイヤーのIDをno_lossリストに追加する。

elif losses[player] == 1:
one_loss.append(player)
プレイヤーの敗北数が1回である場合、そのプレイヤーのIDをone_lossリストに追加する。

例

losses: {3: 2, 6: 2, 7: 1, 5: 1, 8: 1, 9: 2, 4: 1}
all_players: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

プレイヤー	敗北数 (losses[player])	結果リストへの追加
1	0	no_loss[1]
2	0	no_loss[1, 2]
3	2	なし
4	1	one_loss[4]
5	1	one_loss[4, 5]
6	2	なし
7	1	one_loss[4, 5, 7]
8	1	one_loss[4, 5, 7, 8]
9	2	なし
10	0	no_loss[1, 2, 10]

このループが終了すると、no_lossとone_lossは以下のようになる。

• no_loss: [1, 2, 10]
• one_loss: [4, 5, 7, 8]

最後に、コードは [no_loss, one_loss] という形式で結果を返す必要があるので、回答は下記になる。

• [[1, 2, 10], [4, 5, 7, 8]]