[LeetCode] 997. Find the Town Judge (Python3)

요약

• 오직 한 명의 Town Judge는 절대 다른 이를 믿지(trust)않으며, Town Judge가 아닌 이들은 모두 Town Judge를 믿는다. 서로간의 신뢰관계가 담긴 이차원 배열이 주어질 때, Town Judge의 번호를 찾고, 없으면 -1을 반환하라.

풀이

내 풀이

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

• 이 문제는 주어진 조건에 의해 "노드의 수"의 관점에서 보면 => 제약조건이 발생함을 찾을 수 있다! 들어오는 노드는 n-1개, 나가는 노드가 0개여야'만' Town Judge이다.

배운 점

• 그래프 문제는 노드의 개수로 접근해서 풀 수도 있다!!!!

생각

1. 아침부터 안 풀리는 문제들 계속 잡고 풀다가 오게 된 리트코드... 뱅뱅 돌아가는 것 같아서, 다른 사람의 아이디어만 확인하려고 했는데 그 접근방법이 전부였다. 다시 말해서 그 아이디어를 떠올리는 게 포인트다. 인풋이 많아야 사고의 폭을 확장할 수 있다. 공부하자.
2. 당분간은 알고리즘 수업과 관련된 문제를 집중해서 풀어보자!