LeetCode: Find the Town Judgeを解く

問題

May Leetcoding Challange Complementの10日目です。 ブログの解説記事（というかメモ）はとぎれとぎれですが、このコーディングチャレンジ自体は毎日欠かさずやってます。

むかしおじいちゃんが毎日 新聞のクロスワードパズル解いてて、それと同じ感覚なのかな、と思い始めてきました。

leetcode.com

グラフの問題です。 ですが、DFS/BFSやトポロジカルソートや最短経路系ではなく、シンプルに考えれば解法が思いつく問題です。

解き方

The Town Judgeは問題文にも書いてある通り、以下の性質を持っています。

• 村民の誰も信用していない
• 他の村民はみなThe Town Judgeを信用している

ここから以下の2つを数えるハッシュマップ or 配列を作って数え上げれば答えが出せます。

1. trusted[i]: i番目の人を信頼している人の数
2. trusting[i]: i番目の人が信頼している人の数

trusted[i] == N-1 かつ trusting == 0の人がThe Town Judgeになります。

回答

from collections import defaultdict

class Solution:
    def findJudge(self, N: int, trust: List[List[int]]) -> int:
        trusted = defaultdict(int)
        trusting = defaultdict(int)
        for t in trust:
            trusted[t[1]] += 1
            trusting[t[0]] += 1
            
        for i in range(1, N+1):
            if trusted[i] == (N-1) and trusting[i] == 0:
                return i
            
        return -1

さらにこの考え方を推し進めると 以下のように一つの配列 or ハッシュマップで計算できます。

from collections import defaultdict

class Solution:
    def findJudge(self, N: int, trust: List[List[int]]) -> int:
        trusted = defaultdict(int)
        for t in trust:
            trusted[t[1]] += 1
            trusted[t[0]] -= 1
            
        for i in range(1, N+1):
            if trusted[i] == (N-1):
                return i
            
        return -1

計算量

時間計算量: O(N) 空間計算量: O(N)