[leetcode] 997. Find the Town Judge

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

난이도 : Lv.1

 

풀이

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        if not trust:
            if n == 1:
                return 1
            else:
                return -1
        
        relationship = [[] for _ in range(n+1)]
        for a, b in trust:  #a는 b를 신뢰
            relationship[b].append(a)
        
        for i in range(1, n+1):
            if len(relationship[i]) == n-1:
                for t in range(1, n+1):
                    if i in relationship[t]:
                        return -1
                    
                return i
        
        return -1

처음엔 이게 무슨 문젠가,,,했는데 문제를 제대로 안 읽은 탓이었다;;

저지를 제외한 모든 사람들은 저지를 신뢰하지만, 저지는 아무도 신뢰하지 않는다.   <-- 중요

신뢰관계를 나타내는 배열을 만들어서 해당 사람을 믿는 모든 사람들을 추가한다. 
relationship[b] = [a, c, d]   <-- b를 믿는 사람들 a,c,d

저지를 제외한 모든 사람들(n-1)이 믿는 애가 있다면! 걔가 조건을 만족하는지 체크하면 된다.

 

 다른 풀이

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        count = [0] * (n + 1)
        for i, j in trust:
            count[i] -= 1
            count[j] += 1
        for i in range(1, n + 1):
            if count[i] == n - 1:
                return i
        return -1

다른 풀이를 보니 씽크빅! 이렇게 하면 나처럼 2중포문 안 돌고 한번만 돌아도 됨