[leetcode] 997. Find the Town Judge

https://leetcode.com/problems/find-the-town-judge/

 

town judge가 존재하는데 (1) town judge는 아무도 믿지 않는다. 그런데 (2) town judge를 제외한 모든 사람은 town judge를 믿는다. (1)과 (2) 조건을 만족하는 judge는 한 명이다.

 

trust라는 배열이 주어지는데 여기에 없다면 관계는 존재하지 않는다.

 

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

 

이런 input이 있다면, 그 관계는 이렇게 표현할 수 있다.

여기서 1과 2의 outdegree는 각각 1개이고, indegree는 없다.

3을 보면, indegree는 2개 (n-1)이고, outdegree는 없다.

town judge는 indegree가 n-1이고, outdegree는 없음을 알 수 있다.

 

이런 특성을 이용해서 코드를 짰다.

 

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        if not trust:
            if n == 1: return 1
            else: return -1

        relationship = defaultdict(list)
        for a, b in trust:
            if a in relationship:
                relationship[a][0] += 1
            else:
                relationship[a] = [1, 0] # outdegree, indegree
            if b in relationship:
                relationship[b][1] += 1
            else:
                relationship[b] = [0, 1]

        for key, val in relationship.items():
            if val[0] == 0 and val[1] == n-1:
                return key
        return -1

 

 

그런데 내 코드는 상대적으로 runtime이 빠르지 않다.

---

코드를 효율적으로 고쳐보자!

 

우선 defaultdict()을 써야 할까?

어차피 indegree, outdegree를 count 하는 것이므로 2개의 배열을 사용해주면 된다.

그러면 공간 복잡도를 줄일 수 있다.

 

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        if n == 1 and not trust:
            return 1

        trusts = [0] * (n+1)
        trusted_by = [0] * (n+1)
        
        for a, b in trust:
            trusts[a] += 1
            trusted_by[b] += 1

        for i in range(n+1):
            if trusts[i] == 0 and trusted_by[i] == n-1:
                return i
        return -1

 

 

---

구글 개발자가 구글 코딩 테스트를 볼 때 working code를 완성하는 것이 먼저라고 했다.

우선 완성을 한 다음에 optimization을 고민하라고 했다.