ゼロから始めるLeetCode Day9「997. Find the Town Judge」

概要

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

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

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

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

LeetCode

問題

997. Find the Town Judge

この問題は、1からnまでの番号が付けられたn人の住人がいる町で、判事を特定するというもの。
もし判事が存在するなら、以下の3つの条件を満たす。

1. 判事は誰のことも信頼しない。
2. 判事以外のすべての住人は判事を信頼する。
3. 上記の2つの条件を満たす人物は一人だけである。

trustという配列が与えられ、trust[i] = [a, b] は「人物aが人物bを信頼している」という意味。
与えられたnとtrustから、判事が特定できるならその判事の番号を返し、そうでなければ-1を返す。

Example 1:
Input: n = 2, trust = [[1,2]]
Output: 2

Example 2:
Input: n = 3, trust = [[1,3],[2,3]]
Output: 3

Example 3:
Input: n = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1

Constraints:
・1 <= n <= 1000
・0 <= trust.length <= $10^4$
・trust[i].length == 2
・All the pairs of trust are unique.
・$a_i$ != $b_i$
・1 <= $a_i$, $b_i$<= n

解法

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:      
        trusts_count = defaultdict(int)
        trusted_by_count = defaultdict(int)

        for a, b in trust:
            trusts_count[a] += 1
            trusted_by_count[b] += 1

        for i in range(1, n + 1):
            if trusts_count[i] == 0 and trusted_by_count[i] == n - 1:
                return i

        return -1

辞書の初期化

trusts_count = defaultdict(int)
各人が信頼している人数を記録する。キーは人の番号、値はその人が信頼している人数。
defaultdict(int)を使うことで、キーがまだ存在しない場合でも、初めてアクセスされたときに自動的にデフォルト値として 0 が割り当てられる

trusted_by_count = defaultdict(int):
各人が信頼されている人数を記録する。
キーは人の番号、値はその人が信頼されている人数。
同様にdefaultdict(int)で初期化され自動で0が割り当てられる。

信頼関係の集計

for a, b in trust:
    trusts_count[a] += 1
    trusted_by_count[b] += 1

trusts_count[a] += 1
「a」が「b」を信頼しているので、「a」が信頼している人の数を1増やす。

trusted_by_count[b] += 1
「b」が「a」から信頼されているので、「b」が信頼されている人の数を1増やす。

判事の特定

for i in range(1, n + 1):
    if trusts_count[i] == 0 and trusted_by_count[i] == n - 1:
        return i

if trusts_count[i] == 0
現在の人物iが誰も信頼していないという町長の1つ、目の条件をチェックしている。

and trusted_by_count[i] == n - 1
現在の人物iが自分以外の全ての人から信頼されているという町長の2つ目の条件をチェックしている。
n - 1なのは、判事自身は自分を信頼しないため。
もし両方の条件が真であれば、そのiを返して処理を終了する。

例

Input: n = 3, trust = [[1,3],[2,3]]

trust	trusts_count[i]	trusted_by_count[i]
[1,3]	{1: 1}	{3: 1}
[2,3]	{1: 1, 2: 1}	{3: 2}

• trusts_count = {1: 1, 2: 1}
• trusted_by_count = {3: 2}

インデックス	trusts_count[i] == 0 and trusted_by_count[i] == n - 1
1	偽
2	偽
3	真

条件より、3番の人が判事なので関数の戻り値として「3」を返す。